A fast algorithm for Steiner trees

✍ Scribed by L. Kou; G. Markowsky; L. Berman

• Publisher: Springer-Verlag
• Year: 1981
• Tongue: English
• Weight: 248 KB
• Volume: 15
• Category: Article
• ISSN: 0001-5903
• DOI: 10.1007/bf00288961

✦ Synopsis

Given an undirected distance graph G = (V, E, d) and a set S, where V is the set of vertices in G, E is the set of edges in G, d is a distance function which maps E into the set of nonnegative numbers and S___ V is a subset of the vertices of V, the Steiner tree problem is to find a tree of G that spans S with minimal total distance on its edges. In this paper, we analyze a heuristic algorithm for the Steiner tree problem. The heuristic algorithm has a worst case time complexity of O(ISI ]V] 2) on a random access computer and it guarantees to output a tree that spans S with total distance on its edges no more than 2 (1-1) times that of the optimal tree, where l is the number of leaves in the optimal tree.