Domination in Geometric Intersection Graphs

DOI10.1007/978-3-540-78773-0_64zbMath1136.68568OpenAlexW2134616818MaRDI QIDQ5458576

Erlebach, Thomas, Erik Jan van Leeuwen

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_64

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (11)

On pseudo-disk hypergraphs ⋮ On dominating set of some subclasses of string graphs ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ Geometric dominating-set and set-cover via local-search ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ Approximation algorithms for intersection graphs ⋮ The complexity of dominating set in geometric intersection graphs ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Minimum vertex cover in ball graphs through local search ⋮ Dominating set of rectangles intersecting a straight line ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames

Cites Work

• Unnamed Item
• Improved approximation algorithms for geometric set cover
• Hitting sets when the VC-dimension is small
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Unit disk graphs
• Some APX-completeness results for cubic graphs
• On the chromatic number of intersection graphs of convex sets in the plane
• Almost optimal set covers in finite VC-dimension
• On the complexity of the union of fat convex objects in the plane
• A threshold of ln n for approximating set cover
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Separators for sphere-packings and nearest neighbor graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Simple heuristics for unit disk graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• Algorithms – ESA 2004
• Better Approximation Schemes for Disk Graphs
• Approximation and Online Algorithms

This page was built for publication: Domination in Geometric Intersection Graphs