×

Approximation algorithms for the terminal Steiner tree problem. (English) Zbl 1486.68127

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
PDFBibTeX XMLCite
Full Text: Link