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

DOI10.1007/11830924_3MaRDI QIDQ3595415zbMATH OpenOpenAlexFDO

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

(57)

• Line segment disk cover
• Tighter estimates for -nets for disks
• 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
• On line-separable weighted unit-disk coverage and related problems
• 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 PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
• 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
• Unit disk cover problem in 2D
• On connected domination in unit ball graphs
• Sensor cover and double partition
• On the line-separable unit-disk coverage and related problems
• Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• Double Partition: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
• On line-separable weighted unit-disk coverage and related problems
• Geometric cover with outliers removal
• Polynomial time approximation schemes for minimum disk cover problems
• Approximation algorithm for the uniform bounded facility problem
• Unweighted geometric hitting set for line-constrained disks and related problems
• 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
• Minimum clique partition in unit disk graphs
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• Approximation algorithm for uniform bounded facility location problem
• Time efficient k-shot broadcasting in known topology radio networks
• Algorithms for halfplane coverage and related problems
• The subinterval cover problem
• Wireless networking, dominating and packing
• 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
• Geometric covering via extraction theorem
• Approximating k-Connected m-Dominating Sets
• A constant-factor approximation for multi-covering with disks
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• On the line-separable unit-disk coverage and related problems
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• Maximum lifetime connected coverage with two active-phase sensors
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• Distributed connected dominating sets in unit square and 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)