The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(only showing first 100 items - show all)

Routing to reduce the cost of wavelength conversion
Light orthogonal networks with constant geometric dilation
Vertex and edge covers with clustering properties: Complexity and algorithms
Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
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
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
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
The repeater tree construction problem
Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
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
The many facets of upper domination
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
An efficient heuristic algorithm for solving connected vertex cover problem
$(\delta ,\varepsilon)$-ball approximation of a shape: definition and complexity
Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
Guarding orthogonal art galleries with sliding k-transmitters: hardness and approximation
Network pollution games
Vertex deletion problems on chordal graphs
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$
Inapproximability of the Tutte polynomial of a planar graph
Improved Steiner tree algorithms for bounded treewidth
Towards optimal kernel for connected vertex cover in planar graphs
PORA: a Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design
Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
Dominating set of rectangles intersecting a straight line
Maximum independent sets near the upper bound
Algorithms and complexity for a class of combinatorial optimization problems with labelling
Algorithmic aspects of upper edge domination
On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane $\mathbb{R}^2$
Algorithmic aspects of 2-secure domination in graphs
Independent sets in $(P_4+P_4$,triangle)-free graphs
Extension and its price for the connected vertex cover problem
1-line minimum rectilinear Steiner trees and related problems
Solving the absolute 1-center problem in the quickest path case
Algorithmic aspects of broadcast independence
Weighted geometric set cover with rectangles of bounded integer side lengths
New results on independent sets in extensions of $2K_2$-free graphs
Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
The balanced connected subgraph problem for geometric intersection graphs
Complexity of edge monitoring on some graph classes
Domination chain: characterisation, classical complexity, parameterised complexity and approximability
The Steiner tree in $K_{1,r}$-free split graphs -- a dichotomy
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

This page was built for publication: The Rectilinear Steiner Tree Problem is $NP$-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4179026)