(6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
DOI10.1007/978-3-540-69733-6_54zbMATH Open1148.05310OpenAlexW1530712874MaRDI QIDQ3511366FDOQ3511366
Authors: Xiaofeng Gao, Yaochun Huang, Zhao Zhang, Weili Wu 
Publication date: 10 July 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-69733-6_54
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
- Double Partition: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unit disk graphs
- A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Approximations for Steiner trees with minimum number of Steiner points
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
Cited In (12)
- Constant approximation for the lifetime scheduling problem of \(p\)-percent coverage
- Constant-approximation for minimum weight partial sensor cover
- A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
- Sensor cover and double partition
- 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
- PTAS for the minimum weighted dominating set in growth bounded graphs
- A better constant-factor approximation for weighted dominating set in unit disk graph
- A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Wireless networking, dominating and packing
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
This page was built for publication: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3511366)
