An algorithm for the steiner problem in graphs
- 1 September 1982
- Vol. 12 (3) , 323-333
- https://doi.org/10.1002/net.3230120309
Abstract
The Steiner problem in graphs is concerned with finding a set of edges with minimum total weight which connects a given subset of points in a weighted graph. A branch and bound algorithm for solving this problem is presented together with an interesting application to a problem in molecular evolution. Computational experience gained in using the algorithm compares favorably, for certain classes of graphs, with that of existing methods.Keywords
This publication has 9 references indexed in Scilit:
- The Generation of Minimal Trees with a Steiner TopologyJournal of the ACM, 1972
- Steiner's problem in graphs and its implicationsNetworks, 1971
- The steiner problem in graphsNetworks, 1971
- On the Efficiency of the Algorithm for Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1970
- Quasi-linearization and upper and lower bounds for variational problemsQuarterly of Applied Mathematics, 1962
- On the Problem of SteinerCanadian Mathematical Bulletin, 1961
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956