A faster 11/6-approximation algorithm for the Steiner tree problem in graphs
Alex Zelikovsky · Max Planck Digital Library · 1992
The Steiner problem requires a shortest tree spanning a given vertex subset $S$ within graph $G=(V,E)$. There are two 11/6-approximation algorithms with running time $O(VE+VS^2+S^4)$ and $O(VE+VS^2+S^{3+{1\\over 2}})$, respectively. Now we decrease the implementation time to $O(ES+VS^2+VlogV)$.