hide
Free keywords:
-
Abstract:
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)$.