The Rectilinear Steiner Tree Problem is $NP$-Complete
From MaRDI portal
Publication:4179026
DOI10.1137/0132071zbMath0396.05009WikidataQ56338024 ScholiaQ56338024MaRDI QIDQ4179026
David S. Johnson, 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/0132071
Related Items
A probably fast, provably optimal algorithm for rectilinear Steiner trees, Unnamed Item, EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, Subclass of the Steiner problems on a plane with rectilinear metric, The computation of nearly minimal Steiner trees in graphs, Routing in grid graphs by cutting planes, HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES, Algorithms for the Hypergraph and the Minor Crossing Number Problems, Unnamed Item, Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph, A branch-and-price algorithm for the Steiner tree packing problem., Graph theory (algorithmic, algebraic, and metric problems), On better heuristics for Steiner minimum trees, The full Steiner tree problem, Lower bounds for rectilinear Steiner trees in bounded space, Edge-contraction problems, Approximate min-max relations for odd cycles in planar graphs, A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem, Approximating the selected-internal Steiner tree, Routing to reduce the cost of wavelength conversion, On the complexity of a family of generalized matching problems, Approximation algorithms for weighted matching, Two probabilistic results on rectilinear Steiner trees, On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three, On the removal of forbidden graphs by edge-deletion or by edge- contraction, The Steiner problem in phylogeny is NP-complete, Unit disk graphs, Routing in VLSI-layout, On Steiner ratio conjectures, The multi-weighted Steiner tree problem, The role of Steiner hulls in the solution to Steiner tree problems, An integrated approach to routing and via minimization, How to find Steiner minimal trees in Euclidean \(d\)-space, The rectilinear Steiner arborescence problem, Two new criteria for finding Steiner hulls in Steiner tree problems, Aperiodic tiles, Worst-case minimum rectilinear Steiner trees in all dimensions, The point-to-point delivery and connection problems: Complexity and algorithms, A heuristic for Euclidean and rectilinear Steiner problems, Flow network design for manufacturing systems layout, A fast and simple Steiner routing heuristic, Computing optimal rectilinear Steiner trees: A survey and experimental evaluation, Minimal connected enclosures on an embedded planar graph, On the algorithmic complexity of twelve covering and independence parameters of graphs, Stable sets in certain \(P_6\)-free graphs, Forests, colorings and acyclic orientations of the square lattice, Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study, Balancing problems in acyclic networks, The rectilinear class Steiner tree problem for intervals on two parallel lines, The Steiner ratio for the dual normed plane, On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees, The Steiner tree packing problem in VLSI design, The Steiner tree problem in orientation metrics, Deadlock prevention by acyclic orientations, SSTT: Efficient local search for GSI global routing, On the complexity of graph tree partition problems., The Steiner ratio of high-dimensional Banach--Minkowski spaces., A deep-submicron Steiner tree., On approximability of the independent/connected edge dominating set problems, The allocation problem in hardware design, Minimum Steiner trees in normed planes, On the NP-hardness of edge-deletion and -contraction problems, Planar Manhattan local minimal and critical networks, A column generation approach for solving a non-temporal forest harvest model with spatial structure constraints, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], On component-size bounded Steiner trees, A tight lower bound for the Steiner ratio in Minkowski planes, A new bound on the feedback vertex sets in cubic graphs, Packing Steiner trees: Polyhedral investigations, Packing Steiner trees: A cutting plane algorithm and computational results, Steiner minimal trees in \(L^ 2_ p\), Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs, The source location problem with local 3-vertex-connectivity requirements, Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs, Steiner minimal trees in rectilinear and octilinear planes, A primal-dual method for approximating tree cover with two weights, Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees, Unnamed Item, Worst-case ratios of networks in the rectilinear plane, A Primal-Dual Method for Approximating Tree Cover with Two Weights, Optimal Surface Flattening, Complexity and Approximation Results for the Connected Vertex Cover Problem, (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree, Approximating the Generalized Capacitated Tree-Routing Problem, Faster Steiner Tree Computation in Polynomial-Space, Connected Vertex Covers in Dense Graphs, On the hardness of range assignment problems, The Maximum Independent Set Problem in Planar Graphs, Unnamed Item, Unnamed Item, Rectilinear Steiner Trees in Rectangle Trees, The 1-Steiner-Minimal-Tree problem in Minkowski-spaces, Unnamed Item
