An algorithm for the steiner problem in graphs

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.