The Complexity of Computing Steiner Minimal Trees
From MaRDI portal
Publication:4182533
DOI10.1137/0132072zbMath0399.05023WikidataQ105723921 ScholiaQ105723921MaRDI QIDQ4182533
David S. Johnson, Ronald L. Graham, Michael R. Garey
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
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
05-04: Software, source code, etc. for problems pertaining to combinatorics
Related Items
Determining shortest networks in the Euclidean plane, Unnamed Item, The computation of nearly minimal Steiner trees in graphs, HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES, 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\), Steiner minimal trees for bar waves, On better heuristics for Steiner minimum trees, The full Steiner tree problem, A variational approach to the Steiner network problem, A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space, An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space, Approximating the selected-internal Steiner tree, A linear time algorithm for full Steiner trees, Exact computation of Steiner minimal trees in the plane, Steiner minimal trees for regular polygons, Steiner minimal trees on sets of four points, A decomposition theorem on Euclidean Steiner minimal trees, 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 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, 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, A heuristic for Euclidean and rectilinear Steiner problems, The Steiner minimal network for convex configurations, Some remarks on the Steiner problem, Neural and delay based heuristics for the Steiner problem in networks, A neural network for the Steiner minimal tree problem, Some results on greedy algorithm conjectures, Steiner polygons in the Steiner problem, A continuous version of a result of Du and Hwang, On the Steiner ratio in 3-space, Full minimal Steiner trees on lattice sets, Cut and patch Steiner trees for ladders, The Steiner ratio for the dual normed plane, The computational complexity of Steiner tree problems in graded matrices, Non-crossing of plane minimal spanning and minimal T1 networks, The Steiner ratio of high-dimensional Banach--Minkowski spaces., Minimum Steiner trees in normed planes, A class of full Steiner minimal trees, Steiner's problem in double trees, On greedy heuristic for Steiner minimum trees, On component-size bounded Steiner trees, A tight lower bound for the Steiner ratio in Minkowski planes, Steiner minimal trees in \(L^ 2_ p\), On the structure and complexity of the 2-connected Steiner network problem in the plane, A Newton's method for perturbed second-order cone programs, Upper and lower bounds for the lengths of Steiner trees in 3-space, Using structured steiner trees for hierarchical global routing, (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree, Unnamed Item, Steiner Minimal Trees on Zig-Zag Lines, Steiner Minimal Tree for Points on a Circle, The 1-Steiner-Minimal-Tree problem in Minkowski-spaces
