A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in ^d

DOI10.1007/S10732-010-9137-ZMaRDI QIDQ763244zbMATH OpenOpenAlexFDO

Authors Jon W. Van Laarhoven, Jeffrey W. Ohlmann

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

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

Recommendations

• A delaunay triangulation‐based heuristic for the euclidean steiner problem
• New heuristics for the Euclidean Steiner problem in \(\mathbb{R}^n\)
• Two heuristics for the Euclidean Steiner tree problem
• Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions
• Publication:3028682

Cites work

• A delaunay triangulation‐based heuristic for the euclidean steiner problem
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space
• An improved algorithm for computing Steiner minimal trees in Euclidean d-space
• An O(n logn) heuristic for steiner minimal tree problems on the euclidean metric
• An O(N²) heuristic for steiner minimal trees in E³
• Concatenation-based greedy heuristics for the Euclidean Steiner tree problem
• Experimental evaluation of a partitioning algorithm for the steiner tree problem in R² and R³
• How to find Steiner minimal trees in Euclidean \(d\)-space
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• scientific article; zbMATH DE number 3388861 (Why is no real title available?)
• Local search for the Steiner tree problem in the Euclidean plane
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Representation theory of semisimple Hopf algebras
• Steiner Minimal Trees
• Steiner Trees for Ladders
• The Complexity of Computing Steiner Minimal Trees
• Two heuristics for the Euclidean Steiner tree problem

Cited in

(5)

• The Euclidean Steiner tree problem in \(\mathbb{R}^{n}\): A mathematical programming formulation
• New heuristics for the Euclidean Steiner problem in \(\mathbb{R}^n\)
• Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions
• A delaunay triangulation‐based heuristic for the euclidean steiner problem
• A new heuristic for the Euclidean Steiner tree problem in \(\mathbb{R}^n\)

Describes a project that uses

Uses Software

• GeoSteiner
• FindSteinerTree
• SeDuMi
• OR-Library

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q763244)