Geodesic
WORST-CASE RELATIVE PERFORMANCES OF HEURISTICS FOR THE STEINER PROBLEM IN GRAPHS
Acta mathematica Universitatis Comenianae, Tome 60 (1991) no. 2 
J. Plesnik. WORST-CASE RELATIVE PERFORMANCES OF HEURISTICS FOR THE STEINER PROBLEM IN GRAPHS. Acta mathematica Universitatis Comenianae, Tome 60 (1991) no. 2. http://geodesic.mathdoc.fr/item/AMUC_1991_60_2_a10/
@article{AMUC_1991_60_2_a10,
     author = {J. Plesnik},
     title = {WORST-CASE {RELATIVE} {PERFORMANCES} {OF} {HEURISTICS} {FOR} {THE} {STEINER} {PROBLEM} {IN} {GRAPHS}},
     journal = {Acta mathematica Universitatis Comenianae},
     year = {1991},
     volume = {60},
     number = {2},
     url = {http://geodesic.mathdoc.fr/item/AMUC_1991_60_2_a10/}
}
TY  - JOUR
AU  - J. Plesnik
TI  - WORST-CASE RELATIVE PERFORMANCES OF HEURISTICS FOR THE STEINER PROBLEM IN GRAPHS
JO  - Acta mathematica Universitatis Comenianae
PY  - 1991
VL  - 60
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/AMUC_1991_60_2_a10/
ID  - AMUC_1991_60_2_a10
ER  - 
%0 Journal Article
%A J. Plesnik
%T WORST-CASE RELATIVE PERFORMANCES OF HEURISTICS FOR THE STEINER PROBLEM IN GRAPHS
%J Acta mathematica Universitatis Comenianae
%D 1991
%V 60
%N 2
%U http://geodesic.mathdoc.fr/item/AMUC_1991_60_2_a10/
%F AMUC_1991_60_2_a10

Voir la notice de l'article provenant de la source Comenius University

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.