Efficient path and vertex exchange in Steiner tree algorithms

Steiner's problem in a weighted graph requires a tree of minimum total weight spanning a subset of special vertices. In this paper, we formulate efficient routines for greedy exchanges of paths as well as vertices. The heuristic proposed on the basis of these routines consists of three phases: an initialization providing shortest-path information, a module for the selection of Steiner vertices, and an improvement procedure. The latter procedure constitutes a general procedure executable after any heuristic. A spin-off from the second module is a decreased running time for a well-known 11/6 approximation algorithm. The first phase can be replaced by a shortest-path approximation method to obtain a running time order that is quadratic in the number of vertices.