WORST–CASE RELATIVE PERFORMANCES OF HEURISTICS FOR THE STEINER PROBLEM IN GRAPHS

Abstract. The Steiner problem asks for a minimum cost tree spanning a given subset of vertices in a graph (network) with positive edge costs. First we modify the Rayward-Smith heuristic and prove that this does not change its worst-case performance, but the number of iterations is often reduced. Then 9 heuristics are theoretically analysed as to their worst-case relative performances. 1