Dominating set of rectangles intersecting a straight line

DOI10.1007/s10878-020-00685-yzbMath1468.90113OpenAlexW3120918073MaRDI QIDQ2025079

Supantha Pandit

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

zbMATH Keywords

squaresrectanglesminimum dominating setinclined linestraight line\(\mathsf{NP}\)-harddiagonal lineintersecting a linetouching a line

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (1)

Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames

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