An Efficient Approximation Algorithm for the Steiner Tree Problem

Chi-Yeh Chen

The Steiner tree problem is one of the classic and most fundamental $\mathcal{NP}$-hard problems: given an arbitrary weighted graph, seek a minimum-cost tree spanning a given subse…