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

DOI10.1007/978-3-540-69733-6_54zbMath1148.05310OpenAlexW1530712874MaRDI QIDQ3511366

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

zbMATH Keywords

Approximation algorithmDominating SetUnit Disk Graph

Mathematics Subject Classification ID

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

Related Items (5)

Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ PTAS for the minimum weighted dominating set in growth bounded graphs ⋮ Wireless networking, dominating and packing ⋮ Sensor Cover and Double Partition ⋮ Constant-approximation for minimum weight partial sensor cover

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
• 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

This page was built for publication: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs