(6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs

DOI10.1007/978-3-540-69733-6_54MaRDI QIDQ3511366zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Approximation algorithmDominating SetUnit Disk Graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

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

Cites work

• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximations for Steiner trees with minimum number of Steiner points
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Unit disk graphs

Cited in

(13)

• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• A better constant-factor approximation for weighted dominating set in unit disk graph
• PTAS for the minimum weighted dominating set in growth bounded graphs
• Wireless networking, dominating and packing
• Sensor cover and double partition
• Double Partition: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
• Constant-approximation for minimum weight partial sensor cover
• Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
• Constant approximation for the lifetime scheduling problem of \(p\)-percent coverage

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)