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
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, Solving the absolute 1-center problem in the quickest path case, Finding outbreak trees in networks with limited information, Algorithmic aspects of broadcast independence, Weighted geometric set cover with rectangles of bounded integer side lengths, A column generation approach for solving a non-temporal forest harvest model with spatial structure constraints, Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem, Steiner Trees with Bounded RC-Delay, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], On component-size bounded Steiner trees, Unnamed Item, Polynomial algorithms for protein similarity search for restricted mRNA structures, A tight lower bound for the Steiner ratio in Minkowski planes, On Directed Steiner Trees with Multiple Roots, Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs, A 2-approximation NC algorithm for connected vertex cover and tree cover, Computing optimal Steiner trees in polynomial space, New results on independent sets in extensions of \(2K_2\)-free graphs, The Rectilinear Steiner Tree Problem with Given Topology and Length Restrictions, A new bound on the feedback vertex sets in cubic graphs, On planar valued CSPs, Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem, The balanced connected subgraph problem for geometric intersection graphs, Boundary classes for graph problems involving non-local properties, The control complexity of \(r\)-Approval: from the single-peaked case to the general case, On orthogonally guarding orthogonal polygons with bounded treewidth, Complexity of edge monitoring on some graph classes, Packing Steiner trees: Polyhedral investigations, Packing Steiner trees: A cutting plane algorithm and computational results, Steiner trees for hereditary graph classes: a treewidth perspective, Linear kernels for outbranching problems in sparse digraphs, Extending the kernel for planar Steiner tree to the number of Steiner vertices, THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD, Steiner minimal trees in \(L^ 2_ p\), Inapproximability of the Tutte polynomial of a planar graph, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy, Improved Steiner tree algorithms for bounded treewidth, The connected vertex cover problem in \(k\)-regular graphs, Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible, An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}, Towards optimal kernel for connected vertex cover in planar graphs, Parameterized study of Steiner tree on unit disk graphs, On Guarding Orthogonal Polygons with Sliding Cameras, On approximating the \(d\)-girth of a graph, Hardness and inapproximability of convex recoloring problems, Watching systems in graphs: an extension of identifying codes, The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs, On Complexity of Total Vertex Cover on Subcubic Graphs, Complexity and algorithms for the connected vertex cover problem in 4-regular graphs, Complexity results for identifying codes in planar 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, The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study, A primal-dual method for approximating tree cover with two weights, Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees, Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs, PORA: a Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design, Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation, Network pollution games, Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem, Bottleneck Steiner tree with bounded number of Steiner vertices, The Euclidean bottleneck full Steiner tree problem, Worst-case ratios of networks in the rectilinear plane, Relaxing the constraints of clustered planarity, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, A near linear time approximation scheme for Steiner tree among obstacles in the plane, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, NP-hardness results for the aggregation of linear orders into median orders, Computing a tree having a small vertex cover, Dominating set of rectangles intersecting a straight line, Maximum independent sets near the upper bound, Bounding the expected number of rectilinear full Steiner trees, Vertex deletion problems on chordal graphs, Algorithms and complexity for a class of combinatorial optimization problems with labelling, Complexity of Steiner Tree in Split Graphs - Dichotomy Results, Algorithmic aspects of upper edge domination, A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs, Layered graphs: applications and algorithms, On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\), The allocation problem in hardware design, On Approximating the d-Girth of a Graph, Minimum Steiner trees in normed planes, Algorithmic aspects of 2-secure domination in graphs, Nonseparating independent sets of Cartesian product graphs, Independent sets in \((P_4+P_4\),triangle)-free graphs, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, A multivariate analysis of the strict terminal connection problem, A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation, Graphs and Algorithms in Communication Networks on Seven League Boots, Extension and its price for the connected vertex cover problem, On the NP-hardness of edge-deletion and -contraction problems, \(1\)-line minimum rectilinear Steiner trees and related problems, A note on the complexity of locating-total domination in graphs, Advancements on SEFE and partitioned book embedding problems, On the Clustered Steiner Tree Problem, A Primal-Dual Method for Approximating Tree Cover with Two Weights, Planar Manhattan local minimal and critical networks, The maximum clique problem in multiple interval graphs, On the clustered Steiner tree problem, 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, SSTT: Efficient local search for GSI global routing, The many facets of upper domination, NP-completeness and APX-completeness of restrained domination in graphs, A PSO-based timing-driven octilinear Steiner tree algorithm for VLSI routing considering bend reduction, Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology, On the complexity of graph tree partition problems., Complexity of minimum corridor guarding problems, A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem, The Steiner problem in phylogeny is NP-complete, The saga of minimum spanning trees, How hard is it to tell which is a Condorcet committee?, An efficient heuristic algorithm for solving connected vertex cover problem, The Steiner ratio of high-dimensional Banach--Minkowski spaces., Unit disk graphs, Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs, \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity, 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, On finding a shortest isothetic path and its monotonicity inside a digital object, Induced cycles in graphs, Aperiodic tiles, Worst-case minimum rectilinear Steiner trees in all dimensions, Analysis of farthest point sampling for approximating geodesics in a graph, The point-to-point delivery and connection problems: Complexity and algorithms, A heuristic for Euclidean and rectilinear Steiner problems, A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks, Flow network design for manufacturing systems layout, On better heuristics for Steiner minimum trees, Steiner trees with bounded RC-delay, Maximum regular induced subgraphs in \(2P_3\)-free graphs, The within-strip discrete unit disk cover problem, A partition-based relaxation for Steiner trees, The transitive minimum Manhattan subnetwork problem in 3 dimensions, The full Steiner tree problem, Connected vertex covers in dense graphs, Minimal identifying codes in trees and planar graphs with large girth, Graph theory (algorithmic, algebraic, and metric problems), Approximating the selected-internal Steiner tree, Routing to reduce the cost of wavelength conversion, Light orthogonal networks with constant geometric dilation, Lower bounds for rectilinear Steiner trees in bounded space, Vertex and edge covers with clustering properties: Complexity and algorithms, A fast and simple Steiner routing heuristic, Computing optimal rectilinear Steiner trees: A survey and experimental evaluation, Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, Minimal connected enclosures on an embedded planar graph, On the algorithmic complexity of twelve covering and independence parameters of graphs, Edge-contraction problems, 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, A deep-submicron Steiner tree., On approximability of the independent/connected edge dominating set problems, On the complexity of a family of generalized matching problems
