Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs

DOI10.1007/11830924_3zbMath1148.05308OpenAlexW1607840687MaRDI QIDQ3595415

Erlebach, Thomas, Marc Nunkesser, Matúš Mihalák, Christoph Ambühl

Publication date: 28 August 2007

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11830924_3

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (max. 100)

Tighter estimates for \(\epsilon\)-nets for disks ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Approximating \(k\)-connected \(m\)-dominating sets ⋮ Approximation algorithm for uniform bounded facility location problem ⋮ Maximum lifetime connected coverage with two active-phase sensors ⋮ Time efficient \(k\)-shot broadcasting in known topology radio networks ⋮ Improved results on geometric hitting set problems ⋮ PTAS for the minimum weighted dominating set in growth bounded graphs ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ Polynomial time approximation schemes for minimum disk cover problems ⋮ New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs ⋮ Distributed connected dominating sets in unit square and disk graphs ⋮ (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs ⋮ A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs ⋮ Wireless networking, dominating and packing ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Minimum clique partition in unit disk graphs ⋮ Approximating k-Connected m-Dominating Sets ⋮ Unit disk cover problem in 2D ⋮ Approximation Algorithm for the Uniform Bounded Facility Problem ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Discrete unit square cover problem ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ Limits of local search: quality and efficiency ⋮ The within-strip discrete unit disk cover problem ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Computing a tree having a small vertex cover ⋮ An exact algorithm for a class of geometric set-cover problems ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Domination in Geometric Intersection Graphs ⋮ A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Capacitated discrete unit disk cover ⋮ Line segment disk cover ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Sensor Cover and Double Partition ⋮ A better constant-factor approximation for weighted dominating set in unit disk graph ⋮ Constant-approximation for minimum weight partial sensor cover

This page was built for publication: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs