How to find Steiner minimal trees in Euclidean \(d\)-space

DOI10.1007/BF01758756zbMath0751.05028OpenAlexW2088967712MaRDI QIDQ1186793

Warren D. Smith

Publication date: 28 June 1992

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01758756

zbMATH Keywords

Steiner minimal treesregular polytopessubexponential algorithmsGilbert-Pollak conjectureEuclidean \(d\)-spacesensitivity diagrams

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (28)

Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in \(\mathbb{R}^d\) ⋮ On the Steiner ratio in 3-space ⋮ A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ ⋮ A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in \(n\)-space ⋮ Approximate Euclidean Steiner trees ⋮ The Steiner tree problem in orientation metrics ⋮ Extremal networks in $ \lambda$-geometry, where $ \lambda=3,4,6$ ⋮ Gradient-constrained minimum networks. III: Fixed topology ⋮ 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\) ⋮ Swap-vertex based neighborhood for Steiner tree problems ⋮ Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology ⋮ Euclidean Steiner trees optimal with respect to swapping 4-point subtrees ⋮ Unnamed Item ⋮ Approximations and lower bounds for the length of minimal Euclidean Steiner trees ⋮ An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space ⋮ Minimal curvature-constrained networks ⋮ Network modelling of underground mine layout: two case studies ⋮ A novel approach to phylogenetic trees: d‐Dimensional geometric Steiner trees ⋮ Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in \(E^ 3\) ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ Local search for the Steiner tree problem in the Euclidean plane ⋮ 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 }\) ⋮ A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space

Uses Software

• FindSteinerTree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Computing Euclidean maximum spanning trees
• The Steiner ratio conjecture is true for five points
• A linear time algorithm for full Steiner trees
• Exact computation of Steiner minimal trees in the plane
• Hexagonal coordinate systems and Steiner minimal trees
• Steiner minimal trees for regular polygons
• Finding small simple cycle separators for 2-connected planar graphs
• A decomposition theorem on Euclidean Steiner minimal trees
• Some properties of a centroid of a free tree
• On the Problem of Steiner
• An algorithm for the steiner problem in the euclidean plane
• The 1-steiner tree problem
• Convexity and the Steiner tree problem
• An O(n logn) heuristic for steiner minimal tree problems on the euclidean metric
• A shortest augmenting path method for solving minimal perfect matching problems
• Crossing-Free Subgraphs
• Efficient Planarity Testing
• Rectilinear steiner trees: Efficient special-case algorithms
• An Algorithm for Finding Best Matches in Logarithmic Expected Time
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• On Steiner’s Problem with Rectilinear Distance
• Steiner Minimal Trees
• Lower Bounds for Approximation by Nonlinear Manifolds
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• On the Solution of Systems of Equations by the Epsilon Algorithm of Wynn
• The Generation of Minimal Trees with a Steiner Topology
• A note on Fermat's problem
• On Fermat's Problem on the Surface of a Sphere
• On the Betti Numbers of Real Varieties

This page was built for publication: How to find Steiner minimal trees in Euclidean \(d\)-space