Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
From MaRDI portal
Publication:3595415
DOI10.1007/11830924_3zbMATH Open1148.05308OpenAlexW1607840687MaRDI QIDQ3595415FDOQ3595415
Thomas Erlebach, Marc Nunkesser, Christoph Ambühl, Matúš Mihalák
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (46)
- 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
- Approximating \(k\)-connected \(m\)-dominating sets
- Improved results on geometric hitting set problems
- 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
- 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
- PTAS for the minimum weighted dominating set in growth bounded graphs
- Computing a tree having a small vertex cover
- 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
- Domination in Geometric Intersection Graphs
- A PTAS for the Weighted Unit Disk Cover Problem
- Sensor Cover and Double Partition
- 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
- Approximation Algorithm for the Uniform Bounded Facility Problem
- A constant-factor approximation for multi-covering with disks
- Approximation algorithms for the connected sensor cover problem
- 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
- 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)
