A Fast Algorithm for Steiner Trees

Author

Lawrence T. Kou
George Markowsky, Missouri University of Science and TechnologyFollow
Leonard Berman

Abstract

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(|S||V|²) 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/l) times that of the optimal tree, where l is the number of leaves in the optimal tree.

Recommended Citation

L. T. Kou et al., "A Fast Algorithm for Steiner Trees," Acta Informatica, vol. 15, no. 2, pp. 141 - 145, Springer Verlag, Jun 1981.

The definitive version is available at https://doi.org/10.1007/BF00288961

Department(s)

Computer Science

International Standard Serial Number (ISSN)

0001-5903

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1981 Springer Verlag, All rights reserved.

Publication Date

01 Jun 1981