Name
Abstract | ||
|---|---|---|
The Euclidean Steiner tree problem is to find the tree with minimalEuclidean length spanning a set of fixed points in the plane, allowing theaddition of auxiliary points to the set (Steiner points). The problem isNP-hard, so polynomial-time heuristics are desired. We present two suchheuristics, both of which utilize an efficient method for computing alocally optimal tree with a given topology. The first systematically insertsSteiner points between edges of the minimal spanning tree meeting at anglesless than 120 degrees, performing a local optimization at the end. Thesecond begins by finding the Steiner tree for three of the fixed points.Then, at each iteration, it introduces a new fixed point to the tree,connecting it to each possible edge by inserting a Steiner point, andminimizes over all connections, performing a local optimization for each. Wepresent a variety of test cases that demonstrate the strengths andweaknesses of both algorithms. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1023/A:1008285504599 | Journal of Global Optimization |
Keywords | Field | DocType |
Euclidean Steiner tree,Interior-point algorithm | Discrete mathematics,Range tree,Mathematical optimization,Combinatorics,Steiner tree problem,k-minimum spanning tree,K-ary tree,Euclidean minimum spanning tree,Spanning tree,Mathematics,Minimum spanning tree,Interval tree | Journal |
Volume | Issue | ISSN |
13 | 1 | 1573-2916 |
Citations | PageRank | References |
5 | 0.82 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Derek R. Dreyer | 1 | 5 | 0.82 |
| Michael L. Overton | 2 | 634 | 590.15 |