Tighter approximation bounds for minimum CDS in unit disk graphs

DOI10.1007/S00453-011-9512-7zbMATH Open1231.68182OpenAlexW1969793470MaRDI QIDQ652528FDOQ652528

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

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

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)

Cites Work

• A Greedy Heuristic for the Set-Covering Problem
• Title not available (Why is that?)
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Title not available (Why is that?)

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)