On the terminal Steiner tree problem.
We investigate a practical variant of the well-known graph Steiner tree problem. In this variant, every target vertex is required to be a leaf vertex in the solution Steiner tree. We present hardness results for this variant as well as a polynomial time approximation algorithm with performance ratio \(\rho+2\), where \(\rho\) is the best-known approximation ratio for the graph Steiner tree problem.
scientific article; zbMATH DE number 1856446