New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

DOI10.1016/j.tcs.2009.06.022zbMath1209.68389OpenAlexW2155234080MaRDI QIDQ621836

Xianyue Li, Weili Wu, Yuexuan Wang, Feng Zou, Xiao-Hua Xu, Hongwei David Du, Peng-Jun Wan

Publication date: 28 January 2011

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

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

zbMATH Keywords

approximation algorithmpolynomial-time approximation schememinimum-weighted chromatic disk coverminimum-weighted connected dominating setminimum-weighted dominating setnode-weighted Steiner tree

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 (22)

A PTAS for the Weighted Unit Disk Cover Problem ⋮ Approximating \(k\)-connected \(m\)-dominating sets ⋮ Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ Minimum Dominating Set Problem for Unit Disks Revisited ⋮ On the domination polynomial of a digraph: a generation function approach ⋮ APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ PTAS for the minimum weighted dominating set in growth bounded graphs ⋮ Improved solution to data gathering with mobile mule ⋮ Wireless networking, dominating and packing ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ Approximating k-Connected m-Dominating Sets ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ New approximations for Maximum Lifetime Coverage ⋮ Finding minimum weight connected dominating set in stochastic graph based on learning automata ⋮ Computing a tree having a small vertex cover ⋮ On \(f\)-domination: polyhedral and algorithmic results ⋮ Minimizing the total cost of barrier coverage in a linear domain ⋮ Approximation algorithms for the connected sensor cover problem ⋮ An efficient connected dominating set algorithm in WSNS based on the induced tree of the crossed cube ⋮ Sensor Cover and Double Partition ⋮ Constant-approximation for minimum weight partial sensor cover

Cites Work

• Unnamed Item
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Node-weighted Steiner tree approximation in unit disk graphs
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• The broadcast storm problem in a mobile ad hoc network
• 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
• An approximation scheme for some Steiner tree problems in the plane
• Approximations for Steiner trees with minimum number of Steiner points
• Steiner tree problems

This page was built for publication: New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs