Abstract
The first exact algorithm for the obstacle-avoiding Euclidean
Steiner tree problem in the plane (in its most general form) is presented.
The algorithm uses a two-phase framework — based on the generation
and concatenation of full Steiner trees — previously shown to be very
successful for the obstacle-free case. Computational results for moderate
size problem instances are given; instances with up to 150 terminals have
been solved to optimality within a few hours of CPU-time.
Steiner tree problem in the plane (in its most general form) is presented.
The algorithm uses a two-phase framework — based on the generation
and concatenation of full Steiner trees — previously shown to be very
successful for the obstacle-free case. Computational results for moderate
size problem instances are given; instances with up to 150 terminals have
been solved to optimality within a few hours of CPU-time.
| Original language | English |
|---|---|
| Title of host publication | Algorithm Engineering and Experimentation |
| Subtitle of host publication | International Workshop ALENEX'99 Baltimore, MD, USA, January 15--16, 1999 Selected Papers |
| Editors | Michael T. Goodrich, Catherine C. McGeoch |
| Place of Publication | Berlin, Heidelberg |
| Publisher | Springer Berlin Heidelberg |
| Pages | 282-295 |
| Number of pages | 14 |
| ISBN (Print) | 3-540-66227-8 |
| Publication status | Published - 1999 |
Publication series
| Name | Lecture Notes in Computer Science (LNCS, volume 1619) |
|---|
Keywords
- minimum span tree
- steiner tree
- exact algorithm
- steiner point
- steiner tree problem