Dominating set of rectangles intersecting a straight line
From MaRDI portal
Publication:2025079
DOI10.1007/s10878-020-00685-yzbMath1468.90113OpenAlexW3120918073MaRDI QIDQ2025079
Publication date: 11 May 2021
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-020-00685-y
squaresrectanglesminimum dominating setinclined linestraight line\(\mathsf{NP}\)-harddiagonal lineintersecting a linetouching a line
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Max point-tolerance graphs
- Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
- A unified approach to domination problems on interval graphs
- Unit disk graphs
- Liar's dominating set problem on unit disk graphs
- Dominating set on overlap graphs of rectangles intersecting a line
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- A threshold of ln n for approximating set cover
- Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- Planar Formulae and Their Uses
- Dominating Sets in Chordal Graphs
- The Problem of Compatible Representatives
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Approximation schemes for wireless networks
- Domination in Geometric Intersection Graphs
This page was built for publication: Dominating set of rectangles intersecting a straight line
