Probable Performance of Steiner Tree Algorithms
Bernard M. Waxman · Open Scholarship Institutional Repository (Washington University in St. Louis) · 1988
In this paper we consider the probable performance of three polynomial time approximation algorithms for the Steiner tree problem with respect to a specific random graph model. The Steiner problem asks us to find a minimum cost spanning subgraph (tree) for a subset D of modes in a graph.