The Complexity of Computing Steiner Minimal Trees
From MaRDI portal
Publication:4182533
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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items
The 1-Steiner-Minimal-Tree problem in Minkowski-spaces, HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES, Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints, Determining shortest networks in the Euclidean plane, Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks, Minimum Steiner trees on a set of concyclic points and their center, Solving the prize‐collecting Euclidean Steiner tree problem, 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\), The Clustered Selected-Internal Steiner Tree Problem, (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree, O(n log n)-average-time algorithm for shortest network under a given topology, Unnamed Item, Steiner Minimal Trees on Zig-Zag Lines, A Lagrangean-based decomposition approach for the link constrained Steiner tree problem, ON CHARACTERISTIC AREA OF STEINER TREE, Steiner Minimal Tree for Points on a Circle, The local Steiner problem in normed planes, Using structured steiner trees for hierarchical global routing, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, Approximations for Steiner trees with minimum number of Steiner points, Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in \(E^ 3\), Reorganizing topologies of Steiner trees to accelerate their eliminations, Travelling on graphs with small highway dimension, The computation of nearly minimal Steiner trees in graphs, The Steiner Minimal Tree problem in the λ-geometry plane, 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
