Algorithms for dominating set in disk graphs: breaking the n barrier (extended abstract)

DOI10.1007/978-3-642-15775-2_21MaRDI QIDQ3586466zbMATH OpenOpenAlexFDO

Authors Imran A. Pirwani, Matt 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

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

Recommendations

• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Approximation and Online Algorithms

Cited in

(34)

• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• Packing and covering with non-piercing regions
• Dominating set of rectangles intersecting a straight line
• A tight analysis of geometric local search
• 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
• A game theoretic approach for minimal connected dominating set
• Constructing planar support for non-piercing regions
• Minimum vertex cover in ball graphs through local search
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• Simple PTAS's for families of graphs excluding a minor
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• A PTAS for the Weighted Unit Disk Cover Problem
• Approximation algorithms for intersection graphs
• Approximating dominating set on intersection graphs of rectangles and L-frames
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• PTAS for minimum \(k\)-path vertex cover in ball graph
• Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
• Optimality of geometric local search
• Limits of local search: quality and efficiency
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.
• Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains
• 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
• Geometric stabbing via threshold rounding and factor revealing LPs
• A survey on variant domination problems in geometric intersection graphs
• Generalized class cover problem with axis-parallel strips
• Bipartizing (pseudo-)disk graphs: approximation with a ratio better than 3
• Dominating set, independent set, discrete k-center, dispersion, and related problems for planar points in convex position
• On pseudo-disk hypergraphs

This page was built for publication: Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586466)