Chen, Yen Hung; Lin, Ying Chih Approximation algorithms for the terminal Steiner tree problem. (English) Zbl 1486.68127 Appl. Comput. Math. 17, No. 3, 246-255 (2018). Summary: Given a complete graph \(G = (V, E)\) with a weight function on edges and a subset \(R\) of \(V\), the terminal Steiner tree is a Steiner tree in \(G\) with all the vertices of \(R\) as its leaves. The terminal Steiner tree problem is concerned with the determination of a terminal Steiner tree with minimum weight. This paper shows an approximation scheme with performance ratio of \((2\rho- \frac{(\rho\alpha-\rho)}{(\rho\alpha+\rho+2\alpha-6)})\) for the terminal Steiner tree problem, where \(\rho\) is the best-known performance ratio for the Steiner tree problem with any \(a \geq 2\). MSC: 68R10 Graph theory (including graph drawing) in computer science 05C22 Signed and weighted graphs 68W25 Approximation algorithms 68W40 Analysis of algorithms Keywords:approximation algorithms; approximation scheme; Steiner tree; terminal Steiner tree problem; network communication; evolutionary tree reconstruction in biology; telecommunications; NP-completeness PDFBibTeX XMLCite \textit{Y. H. Chen} and \textit{Y. C. Lin}, Appl. Comput. Math. 17, No. 3, 246--255 (2018; Zbl 1486.68127) Full Text: Link