WORST-CASE RELATIVE PERFORMANCES OF HEURISTICS FOR THE STEINER PROBLEM IN GRAPHS
Ján Plesnı́k · 1991
. 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. Introduction In the Steiner problem in graphs (networks) we are given a graph (undirected, without loops and multiple edges) G = (V; E), a positive-valued cost (length) function c : E ! R + , and Z ` V . We are asked to find a minimum cost tree T ` G spanning Z, where the cost of T , c(T ), is the sum of its edge costs. Denote n := jV j, m := jEj and p := jZj. At the present time there are more than 100 papers related to this Steiner problem. Most of them are surveyed by Winter in the excellent paper [19]. For a further work see the very recent survey by Hwang and Richards [7] which gives a vast bibli...