Tighter approximation bounds for minimum CDS in unit disk graphs

DOI10.1007/S00453-011-9512-7MaRDI QIDQ652528zbMATH OpenOpenAlexFDO

Authors Minming Li, Peng-Jun Wan, Frances F. Yao

Publication date 14 December 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-011-9512-7

zbMATH Keywords

approximation algorithmconnected dominating setgeometric analysiswireless ad hoc networks

Mathematics Subject Classification ID

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

Recommendations

• Tighter approximation bounds for minimum CDS in wireless ad hoc networks
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• A new bound on maximum independent set and minimum connected dominating set in unit disk graphs
• A better constant-factor approximation for weighted dominating set in unit disk graph
• On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• scientific article; zbMATH DE number 1896104 (Why is no real title available?)
• scientific article; zbMATH DE number 2209525 (Why is no real title available?)
• Minimum connected dominating sets and maximal independent sets in unit disk graphs

Cited in

(11)

• Making a dominating set of a graph connected
• Approximating 2-cliques in unit disk graphs
• On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs
• Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks
• ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
• Tighter approximation bounds for minimum CDS in wireless ad hoc networks
• 2-edge connected dominating sets and 2-connected dominating sets of a graph
• An efficient connected dominating set algorithm in WSNS based on the induced tree of the crossed cube
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• A new bound on maximum independent set and minimum connected dominating set in unit disk graphs
• A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks

This page was built for publication: Tighter approximation bounds for minimum CDS in unit disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q652528)