On better heuristic for Euclidean Steiner minimum trees
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 431-439
- https://doi.org/10.1109/sfcs.1991.185402
Abstract
Finding a shortest network interconnecting a given set of points in the Euclidean plane (a Steiner minimum tree) is known to be NP-hard. It is shown that there exists a polynomial-time heuristic with a performance ratio bigger than square root 3/2.Keywords
This publication has 13 references indexed in Scilit:
- The Steiner ratio conjecture for six pointsJournal of Combinatorial Theory, Series A, 1991
- On steiner ratio conjecturesAnnals of Operations Research, 1991
- Comments on Bern's probabilistic results on rectilinear Steiner treesAlgorithmica, 1990
- A NEW BOUND FOR EUCLIDEAN STEINER MINIMAL TREESAnnals of the New York Academy of Sciences, 1985
- A new bound for the Steiner ratioTransactions of the American Mathematical Society, 1983
- Some remarks on the Steiner problemJournal of Combinatorial Theory, Series A, 1978
- A Lower Bound for the Steiner Tree ProblemSIAM Journal on Applied Mathematics, 1978
- The Complexity of Computing Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1977
- On Steiner Minimal Trees with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1976
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972