Premium
An algorithm for the steiner problem in graphs
Author(s) -
Shore M. L.,
Foulds L. R.,
Gibbons P. B.
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120309
Subject(s) - steiner tree problem , algorithm , combinatorics , mathematics , graph , computer science , set (abstract data type) , discrete mathematics , programming language
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.