The computation of nearly minimal Steiner trees in graphs
- 1 January 1983
- journal article
- Published by Taylor & Francis in International Journal of Mathematical Education in Science and Technology
- Vol. 14 (1) , 15-23
- https://doi.org/10.1080/0020739830140103
Abstract
The computation of a minimal Steiner tree for a general weighted graph is known to be NP-hard. Except for very simple cases, it is thus computationally impracticable to use an algorithm which produces an exact solution. This paper describes a heuristic algorithm which runs in polynomial time and produces a near minimal solution. Experimental results show that the algorithm performs satisfactorily in the rectilinear case. The paper provides an interesting case study of NP-hard problems and of the important technique of heuristic evaluationKeywords
This publication has 10 references indexed in Scilit:
- A fast algorithm for Steiner treesActa Informatica, 1981
- An O(n log n) algorithm for suboptimal rectilinear Steiner treesIEEE Transactions on Circuits and Systems, 1979
- The Complexity of Computing Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1977
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977
- Rectilinear steiner trees: Efficient special-case algorithmsNetworks, 1977
- On Steiner Minimal Trees with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1976
- On a multinet wiring problemIEEE Transactions on Circuit Theory, 1973
- The steiner problem in graphsNetworks, 1971
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956