Key points are not available for this paper at this time.
Abstract. The classical Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-ln 3 time heuristic that achieves a best-known approximation ratio of 1 + ≈ 1.55 for general graphs 2 and best-known approximation ratios of ≈ 1.28 for both quasi-bipartite graphs (i.e., where no two nonterminals are adjacent) and complete graphs with edge weights 1 and 2. Our method is considerably simpler and easier to implement than previous approaches. We also prove the first known nontrivial performance bound (1.5 · OPT) for the iterated 1-Steiner heuristic of Kahng and Robins in quasi-bipartite graphs.
Robins et al. (Sat,) studied this question.