A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph

DOI10.1016/j.tcs.2008.11.015zbMath1162.68042OpenAlexW2220232453MaRDI QIDQ1006048

Decheng Dai, Chang-Yuan Yu

Publication date: 17 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.11.015

zbMATH Keywords

approximation algorithmdominating setweighted unit disk graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (18)

A PTAS for the Weighted Unit Disk Cover Problem ⋮ Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ Minimum Dominating Set Problem for Unit Disks Revisited ⋮ Approximation algorithm for uniform bounded facility location problem ⋮ APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ PTAS for the minimum weighted dominating set in growth bounded graphs ⋮ Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs ⋮ A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs ⋮ Wireless networking, dominating and packing ⋮ Minimum average routing path clustering problem in multi-hop 2-D underwater sensor networks ⋮ Approximation Algorithm for the Uniform Bounded Facility Problem ⋮ New approximations for Maximum Lifetime Coverage ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Sensor Cover and Double Partition ⋮ A BETTER APPROXIMATION FOR MINIMUM AVERAGE ROUTING PATH CLUSTERING PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS ⋮ Constant-approximation for minimum weight partial sensor cover

Cites Work

• Unnamed Item
• Unnamed Item
• On approximation problems related to the independent set and vertex cover problems
• Unit disk graphs
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Planar Formulae and Their Uses
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Simple heuristics for unit disk graphs

This page was built for publication: A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph