Diané, M.; Plesník, Ján Three new heuristics for the Steiner problem in graphs. (English) Zbl 0763.05024 Acta Math. Univ. Comen., New Ser. 60, No. 1, 105-121 (1991). 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 Keywords:Steiner problem; heuristics; spanning tree heuristic; distances PDFBibTeX XMLCite \textit{M. Diané} and \textit{J. Plesník}, Acta Math. Univ. Comen., New Ser. 60, No. 1, 105--121 (1991; Zbl 0763.05024) Full Text: EuDML EMIS