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

DOI10.1016/J.DISOPT.2007.08.006zbMath1152.90663OpenAlexW1989550031MaRDI 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 branchingEuclidean Steiner problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (10)

Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in \(\mathbb{R}^d\) ⋮ A new second‐order conic optimization model for the Euclidean Steiner tree problem in Rd$\mathbb {R}^d$ ⋮ A new heuristic for the Euclidean Steiner tree problem in \(\mathbb{R}^n\) ⋮ Euclidean Steiner trees optimal with respect to swapping 4-point subtrees ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ Reorganizing topologies of Steiner trees to accelerate their eliminations ⋮ An overview of exact algorithms for the Euclidean Steiner tree problem inn-space ⋮ Insight into the computation of Steiner minimal trees in Euclidean space of general dimension ⋮ Iterated local search algorithms for the Euclidean Steiner tree problem inndimensions ⋮ 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
• 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
• Euclidean Steiner minimum trees: An improved exact algorithm
• 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

This page was built for publication: An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space