Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier

DOI10.1007/978-3-642-15775-2_21zbMath1287.05149OpenAlexW1482161067MaRDI QIDQ3586466

Imran A. Pirwani, Matthew R. Gibson

Publication date: 6 September 2010

Published in: Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15775-2_21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (30)

On pseudo-disk hypergraphs ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ On dominating set of some subclasses of string graphs ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ On the geometric set multicover problem ⋮ Improved and generalized algorithms for burning a planar point set ⋮ On the geometric priority set cover problem ⋮ Geometric dominating-set and set-cover via local-search ⋮ A game theoretic approach for minimal connected dominating set ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Unnamed Item ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Constructing planar support for non-piercing regions ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ Approximation algorithms for intersection graphs ⋮ Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ Packing and covering with non-piercing regions ⋮ Minimum vertex cover in ball graphs through local search ⋮ Limits of local search: quality and efficiency ⋮ Dominating set of rectangles intersecting a straight line ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ Unnamed Item ⋮ Simple PTAS's for families of graphs excluding a minor ⋮ A tight analysis of geometric local search

This page was built for publication: Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier