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

DOI10.1007/11830924_3zbMATH Open1148.05308OpenAlexW1607840687MaRDI QIDQ3595415FDOQ3595415

Authors Thomas Erlebach, Matúš Mihalák, Marc Nunkesser, 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) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• A better constant-factor approximation for weighted dominating set in unit disk graph
• (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph

Cited in

(49)

• Line segment disk cover
• Algorithms for the line-constrained disk coverage and related problems
• Algorithms for the line-constrained disk coverage and related problems
• Capacitated discrete unit disk cover
• Tighter estimates for \(\epsilon\)-nets for disks
• Linear time approximation for dominating sets and independent dominating sets in unit disk graphs
• Approximating \(k\)-connected \(m\)-dominating sets
• Improved results on geometric hitting set problems
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Discrete unit square cover problem
• Constant-approximation for minimum weight partial sensor cover
• A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
• On the line-separable unit-disk coverage and related problems
• Unit disk cover problem in 2D
• Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
• Sensor cover and double partition
• On connected domination in unit ball graphs
• Double Partition: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
• Polynomial time approximation schemes for minimum disk cover problems
• Approximation algorithm for the uniform bounded facility problem
• PTAS for the minimum weighted dominating set in growth bounded graphs
• Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• A better constant-factor approximation for weighted dominating set in unit disk graph
• Graph-Theoretic Concepts in Computer Science
• Domination in Geometric Intersection Graphs
• A PTAS for the Weighted Unit Disk Cover Problem
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• Minimum clique partition in unit disk graphs
• Approximation algorithm for uniform bounded facility location problem
• Time efficient \(k\)-shot broadcasting in known topology radio networks
• A constant-factor approximation algorithm for red-blue set cover with unit disks
• A constant-factor approximation algorithm for red-blue set cover with unit disks
• Approximating k-Connected m-Dominating Sets
• Wireless networking, dominating and packing
• A constant-factor approximation for multi-covering with disks
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• Distributed connected dominating sets in unit square and disk graphs
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Maximum lifetime connected coverage with two active-phase sensors
• (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• An exact algorithm for a class of geometric set-cover problems
• Limits of local search: quality and efficiency
• The within-strip discrete unit disk cover problem

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

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