An algorithm for the steiner problem in the euclidean plane
- 1 September 1985
- Vol. 15 (3) , 323-345
- https://doi.org/10.1002/net.3230150305
Abstract
An algorithm for the exact solution of the Steiner problem in the Euclidean plane is presented. Compared with earlier algorithms, it generates full topologies in a different manner whereby the number of computations is substantially reduced. Furthermore, a large number of full Steiner trees which do not belong to the Steiner minimal tree is identified and discarded by new and efficient tests. The algorithm appears to be considerably faster than any other existing algorithm.Keywords
This publication has 10 references indexed in Scilit:
- A short proof of a result of Pollak on Steiner minimal treesJournal of Combinatorial Theory, Series A, 1982
- An O(n log n) heuristic for steiner minimal tree problems on the euclidean metricNetworks, 1981
- Some remarks on the Steiner problemJournal of Combinatorial Theory, Series A, 1978
- Steiner Trees for LaddersPublished by Elsevier ,1978
- An Improved Program for the Full Steiner Tree ProblemACM Transactions on Mathematical Software, 1977
- The Complexity of Computing Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1977
- On the Efficiency of the Algorithm for Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1970
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1968
- On the Problem of SteinerCanadian Mathematical Bulletin, 1961