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

DOI10.1007/s10732-010-9137-zzbMath1233.68237OpenAlexW1995356291MaRDI QIDQ763244

Jeffrey W. Ohlmann, Jon W. Van Laarhoven

Publication date: 9 March 2012

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-010-9137-z

zbMATH Keywords

Delaunay triangulationSteiner tree

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Uses Software

• SeDuMi
• OR-Library
• GeoSteiner
• FindSteinerTree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space
• An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• How to find Steiner minimal trees in Euclidean \(d\)-space
• Two heuristics for the Euclidean Steiner tree problem
• Local search for the Steiner tree problem in the Euclidean plane
• Concatenation-based greedy heuristics for the Euclidean Steiner tree problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• An O(n logn) heuristic for steiner minimal tree problems on the euclidean metric
• Steiner Trees for Ladders
• The Complexity of Computing Steiner Minimal Trees
• A delaunay triangulation‐based heuristic for the euclidean steiner problem
• Experimental evaluation of a partitioning algorithm for the steiner tree problem in R² and R³
• An O(N²) heuristic for steiner minimal trees in E³
• Steiner Minimal Trees

This page was built for publication: A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in \(\Re ^{d }\)