(6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
DOI10.1007/978-3-540-69733-6_54zbMATH Open1148.05310OpenAlexW1530712874MaRDI QIDQ3511366FDOQ3511366
Weili Wu, Yaochun Huang, Xiaofeng Gao, Zhao Zhang
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 (7)
- Constant-approximation for minimum weight partial sensor cover
- Double Partition: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
- PTAS for the minimum weighted dominating set in growth bounded graphs
- Sensor Cover and Double Partition
- A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
- Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage
- Wireless networking, dominating and packing
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)
