Steiner problem in networks: A survey
- 1 January 1987
- Vol. 17 (2), 129-167
- https://doi.org/10.1002/net.3230170203
Abstract
The problem of determining a minimum cost connected network (i.e., weighted graph) G that spans a given subset of vertices is known in the literature as the Steiner problem in networks. We survey exact algorithms and heuristics which appeared in the published literature. We also discuss problems related to the Steiner problem in networks.This publication has 55 references indexed in Scilit:
- Generalized steiner problem in outerplanar networksBIT Numerical Mathematics, 1985
- Steiner trees, connected domination and strongly chordal graphsNetworks, 1985
- An algorithm for the steiner problem in graphsNetworks, 1984
- Steiner trees, partial 2–trees, and minimum IFI networksNetworks, 1983
- An algorithm for the steiner problem in graphsNetworks, 1982
- An O(n log n) algorithm for suboptimal rectilinear Steiner treesIEEE Transactions on Circuits and Systems, 1979
- An Improved Program for the Full Steiner Tree ProblemACM Transactions on Mathematical Software, 1977
- Cost-minimal trees in directed acyclic graphsMathematical Methods of Operations Research, 1974
- Steiner's problem in graphs and its implicationsNetworks, 1971
- A note on two problems in connexion with graphsNumerische Mathematik, 1959