Two new criteria for finding Steiner hulls in Steiner tree problems

DOI10.1007/BF01758763zbMath0752.05025MaRDI QIDQ1186803

J. Scott Provan

Publication date: 28 June 1992

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmrectilinearSteiner treeSteiner hulls

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05)

Cites Work

• A decomposition theorem on Euclidean Steiner minimal trees
• Shortest enclosing walks and cycles in embedded graphs
• An edge elimination test for the Steiner problem in graphs
• The role of Steiner hulls in the solution to Steiner tree problems
• On the Problem of Steiner
• An algorithm for the steiner problem in the euclidean plane
• Convexity and the Steiner tree problem
• 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
• Optimal enclosing regions in planar graphs
• Rectilinear steiner trees: Efficient special-case algorithms
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Fibonacci heaps and their uses in improved network optimization algorithms
• On Steiner’s Problem with Rectilinear Distance
• Steiner Minimal Trees
• On the Efficiency of the Algorithm for Steiner Minimal Trees
• Steiner's problem in graphs and its implications
• The steiner problem in graphs