A faster approximation algorithm for the Steiner problem in graphs

Abstract

We present an algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V. The set V-S is traditionally denoted as Steiner vertices. The total distance on all edges of this Steiner tree is at most 2(1-1/l) times that of a Steiner minimal tree, where l is the minimum number of leaves in any Steiner minimal tree for the given graph. The algorithm runs in O(|E|log|V|) time in the worst case, where E is the set of all edges and V the set of all vertices in the graph. It improves dramatically on the best previously known bound of O(|S||V|2), unless the graph is very dense and most vertices are Steiner vertices. The essence of our algorithm is to find a generalized minimum spanning tree of a graph in one coherent phase as opposed to the previous multiple steps approach. © 1986 Springer-Verlag.