STEINER PROBLEMS IN GRAPHS: ALGORITHMS AND APPLICATIONS
- 1 January 1983
- journal article
- research article
- Published by Taylor & Francis in Engineering Optimization
- Vol. 7 (1) , 7-16
- https://doi.org/10.1080/03052158308960625
Abstract
Consider an undirected graph G = (V, E) with positive edge weights and a nonempty set S ⊆ V, where Vand E are the sets of vertices and edges of G respectively. The Steiner problem in graphs is that of finding a subgraph of G which spans S and is of minimum total edge weight. In this paper we survey solution procedures for this problem. As the associated decision problem is NP-Complete we place special emphasis on heuristic methods of solution. We also examine special cases, related problems, and applications. The paper concludes with ideas for the development of new, efficient heuristics.Keywords
This publication has 23 references indexed in Scilit:
- The steiner problem in phylogeny is NP-completeAdvances in Applied Mathematics, 1982
- The largest minimal rectilinear steiner trees for a set ofn points enclosed in a rectangle with given perimeterNetworks, 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
- Steiner's problem in graphs and its implicationsNetworks, 1971
- The steiner problem in graphsNetworks, 1971
- Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1968
- On Steiner’s Problem with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1966
- A note on two problems in connexion with graphsNumerische Mathematik, 1959