Abstract
We give polynomial-time algorithms for two special cases of the Steiner problem: (1) the underlying network is planar and all terminals lie within a bounded number of "layers" of a single face, and (2) the problem is the rectilinear Steiner problem and the number of rectilinear convex hulls in the entire "onion" of convex hulls is bounded. Our algorithms build on well-known dynamic programming algorithms. For the second problem, we also use some geometric arguments.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs,Proc. 24th IEEE Symp. on Foundations of Computer Science (1983).
M.W. Bern, Faster exact algorithms for Steiner trees in planar networks, Networks 20(1990)109–120.
D. Bienstock and C.L. Monma, On the complexity of covering vertices by faces in a planar graph, SIAM J. Comput. 17(1988)53–76.
D. Bienstock and C.L. Monma, On embedding planar graphs to minimize certain distance measures, Algorithmica 5(1990)93–110.
S.E. Dreyfus and R.A. Wagner, The Steiner problem in graphs, Networks 1(1972)195–208.
R.E. Erickson, C.L. Monma and A.F. Veinott, Send-and-split method for minimum-concave-cost network flows, Math. Oper. Res. 12(1987)634–664.
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).
M. Hanan, On Steiner's problem with rectilinear distance, SIAM J. Appl. Math. 14(1966)255–265.
F.T. Leighton, private communication (1989).
A.J. Levin, Algorithm for the shortest connection of a group of graph vertices, Sov. Math. Doklady 12(1971)1477–1481.
J.S. Provan, Convexity and the Steiner tree problem, Networks 18(1988)55–72.
J.S. Provan, An approximation scheme for finding Steiner trees with obstacles, SIAM J. Comput. 17(1988)920–934.
W.D. Smith, Studies in computational geometry motivated by mesh generation, Ph.D. Thesis, Department of Mathematics, Princeton University (1988).
C.D. Thomborson, L.L. Deneen and G.M. Shute,Computing a Rectilinear Steiner Minimal Tree in n O(√n) Time, Parallel Algorithms and Architectures, ed. Albrecht et al. (Akademic-Verlag, Berlin, 1987).
P. Winter, Steiner problem in networks: A survey, Networks 17(1987)129–167.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bern, M., Bienstock, D. Polynomially solvable special cases of the Steiner problem in planar networks. Ann Oper Res 33, 403–418 (1991). https://doi.org/10.1007/BF02071979
Issue Date:
DOI: https://doi.org/10.1007/BF02071979