Abstract
An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time0(¦V¦ ¦E¦ + ¦S¦4), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. M. Karp, Reducibility among combinatorial problems, in: R. E. Miller and J. W. Tatcher, eds.,Complexity of Computer Computation, Plenum, New York, 1972, pp. 85–103.
L. Kou, A faster approximation algorithm for the Steiner problem in graphs,Acta Inform.,27 (1990), 369–380.
L. Kou, G. Markowsky, and L. Berman, A fast algorithm for Steiner trees,Acta Inform.,15 (1981), 141–145.
K. Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs,Inform. Process. Lett.,27 (1988), 125–128.
P. Winter, Steiner problem in networks: a survey,Networks,17 (1987), 129–167.
Author information
Authors and Affiliations
Additional information
Communicated by Christos H. Papadimitriou.
Rights and permissions
About this article
Cite this article
Zelikovsky, A.Z. An 11/6-approximation algorithm for the network steiner problem. Algorithmica 9, 463–470 (1993). https://doi.org/10.1007/BF01187035
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01187035