An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space

DOI10.1016/j.disopt.2007.08.006zbMath1152.90663MaRDI QIDQ951125

Kurt M. Anstreicher, Márcia H. C. Fampa

Publication date: 29 October 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2007.08.006

zbMATH Keywords

strong branching; Euclidean Steiner problem

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C27: Combinatorial optimization

Related Items

A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in \(\Re ^{d }\)

Uses Software

• OR-Library
• Mosek
• FindSteinerTree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using a conic formulation for finding Steiner minimal trees
• A linear time algorithm for full Steiner trees
• Exact computation of Steiner minimal trees in the plane
• Hexagonal coordinate systems and Steiner minimal trees
• Applications of second-order cone programming
• How to find Steiner minimal trees in Euclidean \(d\)-space
• Improved computation of plane Steiner minimal trees
• The Steiner tree problem
• The Euclidean Steiner tree problem in \(\mathbb{R}^{n}\): A mathematical programming formulation
• Disproofs of generalized Gilbert-Pollak conjecture on the Steiner ratio in three or more dimensions
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On the Problem of Steiner
• An algorithm for the steiner problem in the euclidean plane
• The Complexity of Computing Steiner Minimal Trees
• A Computational Study of Search Strategies for Mixed Integer Programming
• An Efficient Primal-Dual Interior-Point Method for Minimizing a Sum of Euclidean Norms
• Steiner Minimal Trees