Paper Info
Title
A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in ℜd.
Abstract
We present a heuristic for the Euclidean Steiner tree problem in R-d for d >= 2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to identify the Steiner points to remove, and second-order cone programming to optimize the location of the remaining Steiner points. Unlike other ESTP heuristics relying upon Delaunay triangulation, we insert Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. We govern this neighbor generation procedure with a local search framework that extends effectively into higher dimensions. We present computational results on benchmark test problems in R-d for 2 <= d <= 5.
Year
DOI
Venue
2011
10.1007/s10732-010-9137-z
JOURNAL OF HEURISTICS
Keywords
DocType
Volume
Steiner tree,Delaunay triangulation
Journal
17.0
Issue
ISSN
Citations 
4
1381-1231
1
PageRank 
References 
Authors
0.39
10
2
Name
Order
Citations
PageRank
Jon W. Van Laarhoven110.72
Jeffrey W. Ohlmann216314.83