A better constant-factor approximation for weighted dominating set in unit disk graph

DOI10.1007/S10878-008-9146-0zbMath1184.05090OpenAlexW2063726026MaRDI QIDQ1037452

Xiaofeng Gao, Weili Wu, Zhao Zhang, Yaochun Huang

Publication date: 16 November 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-008-9146-0

zbMATH Keywords

wireless networkconnected dominating setunit disk graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (15)

A PTAS for the Weighted Unit Disk Cover Problem ⋮ Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ Node-weighted Steiner tree approximation in unit disk graphs ⋮ Minimum Dominating Set Problem for Unit Disks Revisited ⋮ Approximation algorithm for uniform bounded facility location problem ⋮ Maximum lifetime connected coverage with two active-phase sensors ⋮ APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ Polynomial time approximation schemes for minimum disk cover problems ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ New approximations for Maximum Lifetime Coverage ⋮ Minimizing the total cost of barrier coverage in a linear domain ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Sensor Cover and Double Partition ⋮ Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On approximation problems related to the independent set and vertex cover problems
• Unit disk graphs
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Planar Formulae and Their Uses
• Approximation algorithms for NP-complete problems on planar graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Simple heuristics for unit disk graphs
• Chebyshev's approximation algorithms and applications

This page was built for publication: A better constant-factor approximation for weighted dominating set in unit disk graph