×

Three new heuristics for the Steiner problem in graphs. (English) Zbl 0763.05024

Summary: Three practically successful heuristics are presented and analysed. They include the known spanning tree heuristic (STH). One of the heuristics chooses Steiner vertices by STH and the other two heuristics according to their sum of all distances to the special vertices. The theoretical worst-case performance ratio remains the same as for STH.

MSC:

05C05 Trees
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: EuDML EMIS