An algorithm for the Steiner problem in graphs, Networks, vol.14, no.1, 1984, pp147-159
In this paper we consider the Steiner problem in graphs. This is the problem of connecting together, at minium cost, a number of vertices in an undirected graph. We present two lower bounds for the problems, these bounds being based on two separate lagrangian relaxations of a zero-one integer programming formulation of the problem. Problem reduction tests derived from both the original problem and the lagrangian relaxations are given. Incorporating the bounds and the reduction tests into a tree search procedure enables us to solve problems involving the connection of up to 50 vertices in a graph with 200 undirected arcs and 100 vertices.