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

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