Polynomially solvable special cases of the Steiner problem in planar networks

DOI10.1007/BF02071979zbMath0745.90071OpenAlexW2066137891MaRDI QIDQ1179749

Bienstock, Daniel, Marshall W. Bern

Publication date: 27 June 1992

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02071979

zbMATH Keywords

weighted graphpolynomial timeplanar networkSteiner problem on networksminimum length tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (4)

Improved Steiner tree algorithms for bounded treewidth ⋮ A linear programming based approach to the Steiner tree problem with a fixed number of terminals ⋮ The role of Steiner hulls in the solution to Steiner tree problems ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of embedding planar graphs to minimize certain distance measures
• Convexity and the Steiner tree problem
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Steiner problem in networks: A survey
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Faster exact algorithms for steiner trees in planar networks
• On Steiner’s Problem with Rectilinear Distance
• The steiner problem in graphs

This page was built for publication: Polynomially solvable special cases of the Steiner problem in planar networks