Solving a Steiner Tree Problem on a Graph Using Branch and Cut, ORSA Journal on Computing
In this paper we report computational experience with a branch and cut solver for the Steimer tree problem on a graph. The problem instances include complete graphs, randomly generated sparse graphs and grid graphs. The edge weights are either randomly generated or are the Euclidean distance between the endnodes that are placed at random on the plane. The effect of changing various problem parameters on solution time is studied.
Sunil Chopra, Edgar R. Gorres, M. R. Rao
Chopra, Sunil, Edgar R. Gorres, and M. R. Rao. 1992. Solving a Steiner Tree Problem on a Graph Using Branch and Cut. ORSA Journal on Computing. 4(3): 320-335.