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 algorithmgeometric analysiswireless ad hoc networksconnected dominating set

Mathematics Subject Classification ID

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

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

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

Cited in

(11)

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