WORST-CASE RELATIVE PERFORMANCES OF HEURISTICS FOR THE STEINER PROBLEM IN GRAPHS
J. PLESNIK
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.
AMS subject classification.
68E10
Keywords.
Graph, network, Steiner tree, approximation algorithm, heuristic, worst case
Download: Adobe PDF Compressed Postscript
Compressed Postscript 
