The Rectilinear Steiner Tree Problem is $NP$-Complete
From MaRDI portal
Publication:4179026
DOI10.1137/0132071zbMath0396.05009OpenAlexW2020112047WikidataQ56338024 ScholiaQ56338024MaRDI QIDQ4179026
Michael R. Garey, David S. Johnson
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 (only showing first 100 items - show all)
Rectilinear Steiner Trees in Rectangle Trees ⋮ The 1-Steiner-Minimal-Tree problem in Minkowski-spaces ⋮ HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES ⋮ On the complexity of approximating and illuminating three-dimensional convex polyhedra ⋮ Optimal urban sewer layout design using Steiner tree problems ⋮ Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line ⋮ Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs ⋮ Routing in grid graphs by cutting planes ⋮ A probably fast, provably optimal algorithm for rectilinear Steiner trees ⋮ On the computational difficulty of the terminal connection problem ⋮ Extremal networks in $ \lambda$-geometry, where $ \lambda=3,4,6$ ⋮ Approximating power node-deletion problems ⋮ The firebreak problem ⋮ Gamma deployment problem in grids: hardness and new integer linear programming formulation ⋮ Parameterized complexity of path set packing ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ Optimal Surface Flattening ⋮ Complexity and Approximation Results for the Connected Vertex Cover Problem ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Weighted connected matchings ⋮ (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree ⋮ Approximating the Generalized Capacitated Tree-Routing Problem ⋮ Computing maximum matchings in temporal graphs ⋮ Balanced substructures in bicolored graphs ⋮ Sequentially swapping tokens: further on graph classes ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ On 3-degree 4-chordal graphs ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Unnamed Item ⋮ Algorithms for the Hypergraph and the Minor Crossing Number Problems ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Connected Vertex Covers in Dense Graphs ⋮ On the hardness of range assignment problems ⋮ Monitoring the edges of a graph using distances ⋮ On the computational complexity of centers locating in a graph ⋮ Unnamed Item ⋮ Contracting to a longest path in H-free graphs ⋮ THE MINIMUM GUARDING TREE PROBLEM ⋮ The word and geodesic problems in free solvable groups ⋮ The local Steiner problem in normed planes ⋮ The Maximum Independent Set Problem in Planar Graphs ⋮ EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION ⋮ A branch-and-price algorithm for the Steiner tree packing problem. ⋮ On triangulating planar graphs under the four-connectivity constraint ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Covering and packing of triangles intersecting a straight line ⋮ Unnamed Item ⋮ Travelling on graphs with small highway dimension ⋮ Unnamed Item ⋮ The lexicographically first maximal subgraph problems:P-completeness andNC algorithms ⋮ Subclass of the Steiner problems on a plane with rectilinear metric ⋮ Beyond Clustered Planar Graphs ⋮ Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph ⋮ The computation of nearly minimal Steiner trees in graphs ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction* ⋮ On Covering Segments with Unit Intervals ⋮ Vertex Deletion Problems on Chordal Graphs ⋮ Balancing problems in acyclic networks ⋮ The rectilinear class Steiner tree problem for intervals on two parallel lines ⋮ Some observations on holographic algorithms ⋮ \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point ⋮ Approximability and hardness of geometric hitting set with axis-parallel rectangles ⋮ On the terminal connection problem ⋮ Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs ⋮ On the minimum corridor connection problem and other generalized geometric problems ⋮ Bottleneck bichromatic full Steiner trees ⋮ Safe sets in graphs: graph classes and structural parameters ⋮ A simple proof that the \((n^{2} - 1)\)-puzzle is hard ⋮ Planar graphs have independence ratio at least 3/13 ⋮ A better constant-factor approximation for selected-internal Steiner minimum tree ⋮ Roman domination in subgraphs of grids ⋮ Approximation algorithms for weighted matching ⋮ Two probabilistic results on rectilinear Steiner trees ⋮ The Steiner ratio for the dual normed plane ⋮ Embedding rectilinear Steiner trees with length restrictions ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees ⋮ The Steiner tree packing problem in VLSI design ⋮ Approximate min-max relations for odd cycles in planar graphs ⋮ On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three ⋮ The clique problem in ray intersection graphs ⋮ The repeater tree construction problem ⋮ The Steiner tree problem in orientation metrics ⋮ A \(9k\) kernel for nonseparating independent set in planar graphs ⋮ Secluded connectivity problems ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 ⋮ Deadlock prevention by acyclic orientations ⋮ Interdiction problems on planar graphs ⋮ On the removal of forbidden graphs by edge-deletion or by edge- contraction ⋮ Approximating capacitated tree-routings in networks ⋮ Guarding a set of line segments in the plane ⋮ Minimum rectilinear Steiner tree of \(n\) points in the unit square ⋮ SCIP-Jack -- a solver for STP and variants with parallelization extensions ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ On the complexity of the representation of simplicial complexes by trees ⋮ Flattening topologically spherical surface
This page was built for publication: The Rectilinear Steiner Tree Problem is $NP$-Complete
