ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS

DOI10.1142/S1793830909000105zbMath1178.68680OpenAlexW2147780956MaRDI QIDQ3634205

Weili Wu, Yuexuan Wang, Xianyue Li, Xiaofeng Gao

Publication date: 23 June 2009

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830909000105

zbMATH Keywords

connected dominating setmaximal independent setunit disk graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Communication networks in operations research (90B18) 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

New dominating sets in social networks, Unnamed Item, Improved linear problem kernel for planar connected dominating set, Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks, A new bound on maximum independent set and minimum connected dominating set in unit disk graphs, A greedy algorithm for the fault-tolerant connected dominating set in a general graph, On positive influence dominating sets in social networks, A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks, Wireless networking, dominating and packing, Locating battery charging stations to facilitate almost shortest paths, TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET, An efficient connected dominating set algorithm in WSNS based on the induced tree of the crossed cube

Cites Work

• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Unit disk graphs
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Approximation schemes for covering and packing problems in image processing and VLSI
• 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