Lecture Notes in Computer Science, 2002, Volume 2461/2002, 237-266, DOI: 10.1007/3-540-45749-6_66

An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem

Benny K. Nielsen, Pawel Winter and Martin Zachariasen

View Related Documents

Abstract

An exact algorithm to solve the Steiner tree problem for uniform orientation metrics in the plane is presented. The algorithm is based on the two-phase model, consisting of full Steiner tree (FST) generation and concatenation, which has proven to be very successfulf or the rectilinear and Euclidean Steiner tree problems. By applying a powerful canonicalf orm for the FSTs, the set of optimal solutions is reduced considerably. Computational results both for randomly generated problem instances and VLSI design instances are provided. The new algorithm solves most problem instances with 100 terminals in seconds, and problem instances with up to 10000 terminals have been solved to optimality.
It has not been proved that the problem is NP-hard for every value of λ, but we strongly conjecture this to be the case.

Fulltext Preview

Image of the first page of the fulltext document