Abstract
We present a computational study of exact algorithms for the Euclidean and rectilinear Steiner tree problems in the plane. These algorithms --- which are based on the generation and concatenation of full Steiner trees --- are much more efficient than other approaches and allow exact solutions of problem instances with more than 2000 terminals. The full Steiner tree generation algorithms for the two problem variants share many algorithmic ideas and the concatenation part is identical (integer programming formulation solved by branch-and-cut). Performance statistics for randomly generated instances, public library instances and ``difficult'' instances with special structure are presented. Also, results on the comparative performance on the two problem variants are given.
Original language | English |
---|---|
Title of host publication | Advances in Steiner Trees |
Editors | Ding-Zhu Du, J. M. Smith, J. H. Rubinstein |
Place of Publication | Boston, MA |
Publisher | Springer US |
Pages | 81-116 |
Number of pages | 36 |
ISBN (Print) | 978-1-4757-3171-2 |
DOIs | |
Publication status | Published - 2000 |
Keywords
- steiner tree problem
- Algorithms