Pages that link to "Item:Q4179026"
From MaRDI portal
The following pages link to The Rectilinear Steiner Tree Problem is $NP$-Complete (Q4179026):
Displaying 50 items.
- Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs (Q290201) (← links)
- Planar graphs have independence ratio at least 3/13 (Q311579) (← links)
- Roman domination in subgraphs of grids (Q324726) (← links)
- Embedding rectilinear Steiner trees with length restrictions (Q344768) (← links)
- A sufficient condition to extend polynomial results for the maximum independent set problem (Q344869) (← links)
- The clique problem in ray intersection graphs (Q377488) (← links)
- A \(9k\) kernel for nonseparating independent set in planar graphs (Q385964) (← links)
- Flattening topologically spherical surface (Q431923) (← links)
- NP-completeness and APX-completeness of restrained domination in graphs (Q442103) (← links)
- Complexity of minimum corridor guarding problems (Q456091) (← links)
- The saga of minimum spanning trees (Q458468) (← links)
- How hard is it to tell which is a Condorcet committee? (Q459394) (← links)
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs (Q477653) (← links)
- On finding a shortest isothetic path and its monotonicity inside a digital object (Q499711) (← links)
- Induced cycles in graphs (Q503635) (← links)
- A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks (Q512868) (← links)
- Steiner trees with bounded RC-delay (Q527413) (← links)
- The within-strip discrete unit disk cover problem (Q528480) (← links)
- A partition-based relaxation for Steiner trees (Q535014) (← links)
- Graph theory (algorithmic, algebraic, and metric problems) (Q581419) (← links)
- Approximating capacitated tree-routings in networks (Q630195) (← links)
- Guarding a set of line segments in the plane (Q630591) (← links)
- Analysis of farthest point sampling for approximating geodesics in a graph (Q679744) (← links)
- On better heuristics for Steiner minimum trees (Q687085) (← links)
- Maximum regular induced subgraphs in \(2P_3\)-free graphs (Q690473) (← links)
- The full Steiner tree problem (Q702772) (← links)
- Lower bounds for rectilinear Steiner trees in bounded space (Q750175) (← links)
- Edge-contraction problems (Q794164) (← links)
- On the terminal connection problem (Q831820) (← links)
- On the minimum corridor connection problem and other generalized geometric problems (Q833722) (← links)
- A better constant-factor approximation for selected-internal Steiner minimum tree (Q848949) (← links)
- Approximate min-max relations for odd cycles in planar graphs (Q877199) (← links)
- An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 (Q891823) (← links)
- Interdiction problems on planar graphs (Q897609) (← links)
- On the complexity of the representation of simplicial complexes by trees (Q905846) (← links)
- A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem (Q920030) (← links)
- The transitive minimum Manhattan subnetwork problem in 3 dimensions (Q968145) (← links)
- Connected vertex covers in dense graphs (Q974753) (← links)
- Minimal identifying codes in trees and planar graphs with large girth (Q976158) (← links)
- Approximating the selected-internal Steiner tree (Q995588) (← links)
- Routing to reduce the cost of wavelength conversion (Q1005233) (← links)
- Light orthogonal networks with constant geometric dilation (Q1013080) (← links)
- Vertex and edge covers with clustering properties: Complexity and algorithms (Q1026225) (← links)
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation (Q1028460) (← links)
- On the complexity of a family of generalized matching problems (Q1068535) (← links)
- Approximation algorithms for weighted matching (Q1102118) (← links)
- Two probabilistic results on rectilinear Steiner trees (Q1105495) (← links)
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three (Q1123898) (← links)
- On the removal of forbidden graphs by edge-deletion or by edge- contraction (Q1146698) (← links)
- The Steiner problem in phylogeny is NP-complete (Q1167073) (← links)
