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.
Original language | English |
---|---|
Title of host publication | Algorithms ESA 2002 |
Subtitle of host publication | 10th annual European symposium |
Editors | Rolf Möhring, Rajeev Raman |
Place of Publication | Germany |
Publisher | Springer Berlin Heidelberg |
Pages | 760-772 |
Number of pages | 12 |
Edition | 1 |
ISBN (Electronic) | 978-3-540-45749-7 |
ISBN (Print) | 978-3-540-44180-9 |
DOIs | |
Publication status | Published - 2002 |
Event | European Symposium on Algorithms - Rome, Italy Duration: 17 Sept 2002 → 21 Sept 2002 Conference number: 10 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 2461 |
Conference
Conference | European Symposium on Algorithms |
---|---|
Country/Territory | Italy |
City | Rome |
Period | 17/09/02 → 21/09/02 |
Keywords
- minimum span tree
- exact a
- steiner point
- steiner tree problem
- steiner minimum tree