The Complexity of Computing Steiner Minimal Trees

DOI10.1137/0132072zbMath0399.05023OpenAlexW2060380213WikidataQ105723921 ScholiaQ105723921MaRDI QIDQ4182533

Michael R. Garey, David S. Johnson, Ronald L. Graham

Publication date: 1977

Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0132072

zbMATH Keywords

ComplexityComputing Steiner Minimal Trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (only showing first 100 items - show all)

Exact computation of Steiner minimal trees in the plane ⋮ Some results on greedy algorithm conjectures ⋮ Steiner minimal trees for regular polygons ⋮ Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in \(\mathbb{R}^d\) ⋮ Steiner polygons in the Steiner problem ⋮ A continuous version of a result of Du and Hwang ⋮ Bottleneck bichromatic full Steiner trees ⋮ Steiner tree problem with minimum number of Steiner points and bounded edge-length ⋮ Steiner minimal trees on sets of four points ⋮ On greedy heuristic for Steiner minimum trees ⋮ On the Steiner ratio in 3-space ⋮ On component-size bounded Steiner trees ⋮ A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in \(n\)-space ⋮ A tight lower bound for the Steiner ratio in Minkowski planes ⋮ A better constant-factor approximation for selected-internal Steiner minimum tree ⋮ Largest and smallest convex hulls for imprecise points ⋮ Full minimal Steiner trees on lattice sets ⋮ Cut and patch Steiner trees for ladders ⋮ A Newton's method for perturbed second-order cone programs ⋮ Upper and lower bounds for the lengths of Steiner trees in 3-space ⋮ Approximation schemes for node-weighted geometric Steiner tree problems ⋮ The Steiner ratio for the dual normed plane ⋮ A decomposition theorem on Euclidean Steiner minimal trees ⋮ Approximate Euclidean Steiner trees ⋮ The computational complexity of Steiner tree problems in graded matrices ⋮ Non-crossing of plane minimal spanning and minimal T1 networks ⋮ On a nonconvex MINLP formulation of the Euclidean Steiner tree problem in \(n\)-space: missing proofs ⋮ THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD ⋮ Steiner minimal trees in \(L^ 2_ p\) ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 ⋮ Gradient-constrained minimum networks. III: Fixed topology ⋮ Minimum rectilinear Steiner tree of \(n\) points in the unit square ⋮ Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\) ⋮ Smoothed analysis of partitioning algorithms for Euclidean functionals ⋮ Geometric multicut: shortest fences for separating groups of objects in the plane ⋮ The Steiner problem in phylogeny is NP-complete ⋮ Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time ⋮ The saga of minimum spanning trees ⋮ Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane ⋮ Euclidean Steiner trees optimal with respect to swapping 4-point subtrees ⋮ The Steiner ratio of high-dimensional Banach--Minkowski spaces. ⋮ The Steiner ratio conjecture for six points ⋮ Some upper bounds for minimal trees ⋮ A primer of the Euclidean Steiner problem ⋮ On Steiner ratio conjectures ⋮ Minimal length tree networks on the unit sphere ⋮ The role of Steiner hulls in the solution to Steiner tree problems ⋮ On graphs preserving rectilinear shortest paths in the presence of obstacles ⋮ On the structure and complexity of the 2-connected Steiner network problem in the plane ⋮ A proof of the Gilbert-Pollak conjecture on the Steiner ratio ⋮ How to find Steiner minimal trees in Euclidean \(d\)-space ⋮ Graham's problem on shortest networks for points on a circle ⋮ Improved computation of plane Steiner minimal trees ⋮ Steiner minimal trees for a class of zigzag lines ⋮ Two new criteria for finding Steiner hulls in Steiner tree problems ⋮ The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study ⋮ An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space ⋮ A heuristic for Euclidean and rectilinear Steiner problems ⋮ On the history of the Euclidean Steiner tree problem ⋮ On better heuristics for Steiner minimum trees ⋮ Bottleneck Steiner tree with bounded number of Steiner vertices ⋮ Breakout local search for the Steiner tree problem with revenue, budget and hop constraints ⋮ The Steiner minimal network for convex configurations ⋮ The Euclidean bottleneck full Steiner tree problem ⋮ Discrete particle swarm optimization for the minimum labelling Steiner tree problem ⋮ Probabilistic properties of topologies of minimal fillings of finite metric spaces ⋮ The full Steiner tree problem ⋮ Variable neighbourhood search for the minimum labelling Steiner tree problem ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ On the restricted 1-Steiner tree problem ⋮ Steiner minimal trees for bar waves ⋮ An efficient algorithm for the Steiner tree problem with revenue, bottleneck and hop objective functions ⋮ Approximating the selected-internal Steiner tree ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ Some remarks on the Steiner problem ⋮ On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\) ⋮ Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem ⋮ Minimum Steiner trees in normed planes ⋮ The Steiner problem on surfaces of revolution ⋮ An Algorithm to Find the Link Constrained Steiner Tree in Undirected Graphs ⋮ 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 class of full Steiner minimal trees ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ On the restricted \(k\)-Steiner tree problem ⋮ Neural and delay based heuristics for the Steiner problem in networks ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem ⋮ Isoperimetric enclosures ⋮ On the Clustered Steiner Tree Problem ⋮ Steiner's problem in double trees ⋮ Monochromatic geometric \(k\)-factors for bicolored point sets with auxiliary points ⋮ A linear time algorithm for full Steiner trees ⋮ A variational approach to the Steiner network problem ⋮ Reducing the diameter of a unit disk graph via node addition ⋮ A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space ⋮ A neural network for the Steiner minimal tree problem ⋮ On the clustered Steiner tree problem

This page was built for publication: The Complexity of Computing Steiner Minimal Trees