Heuristics for the Steiner problem in graphs

The Steiner problem in graphs (networks) is to find a minimum cost tree spanning a given subset Z of vertices in a graph G with positive edge costs. The paper presents a new worst-case performance analysis of the contraction heuristic. Also an improved version of this heuristic is suggested and analysed. The main contribution is a proof of certain incomparability of some known heuristics. The paper presents examples for which the heuristics extremely outperform each other in terms of the quality of the solution.