Tighter approximation bounds for minimum CDS in unit disk graphs

DOI10.1007/s00453-011-9512-7zbMath1231.68182OpenAlexW1969793470MaRDI QIDQ652528

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 analysisconnected dominating setwireless ad hoc networks

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) Distributed systems (68M14) Approximation algorithms (68W25)

Related Items (4)

Making a dominating set of a graph connected ⋮ A better approximation for constructing virtual backbone in 3D 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

Cites Work

• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• A Greedy Heuristic for the Set-Covering Problem
• Unnamed Item
• Unnamed Item

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