On the restricted \(k\)-Steiner tree problem

DOI10.1007/s10878-021-00808-zzbMath1504.90111OpenAlexW3199358935MaRDI QIDQ2084651

Anthony D'Angelo, Stephane Durocher, Prosenjit Bose

Publication date: 18 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00808-z

zbMATH Keywords

combinatorial optimizationcomputational geometrySteiner point restrictionsminimum \(k\)-Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact algorithms for the bottleneck Steiner tree problem
• On exact solutions to the Euclidean bottleneck Steiner tree problem
• An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs
• The power of geometric duality
• Steiner minimal trees for a class of zigzag lines
• Transitions in geometric minimum spanning trees
• Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs
• Short trees in polygons
• Full minimal Steiner trees on lattice sets
• Minimal Steiner trees for rectangular arrays of lattice points
• A constrained minimum spanning tree problem
• On the complexity of the Steiner problem
• Approximating geometric bottleneck shortest paths
• Minimal Steiner trees for \(2^ k \times 2^ k\) square lattices
• On the restricted 1-Steiner tree problem
• On the history of the Euclidean Steiner tree problem
• Generalised \(k\)-Steiner tree problems in normed planes
• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Steiner Trees for Terminals Constrained to Curves
• Fast Algorithms for Finding Nearest Common Ancestors
• Steiner Minimal Trees on Zig-Zag Lines
• Constructing Arrangements of Lines and Hyperplanes with Applications
• The 1-steiner tree problem
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Degree-five Steiner points cannot reduce network costs for planar sets
• On the Zone Theorem for Hyperplane Arrangements
• Finding Minimum Spanning Trees
• Steiner Trees for Ladders
• The Complexity of Computing Steiner Minimal Trees
• Steiner Minimal Trees