A new bound on maximum independent set and minimum connected dominating set in unit disk graphs

DOI10.1007/s10878-013-9690-0zbMath1333.90140OpenAlexW2020480064MaRDI QIDQ887860

Yingfan L. Du, Hongmin W. Du

Publication date: 3 November 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9690-0

zbMATH Keywords

maximum independent setminimum connected dominating setunit disk graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (2)

Making a dominating set of a graph connected ⋮ Sensor network topology design and analysis for efficient data gathering by a mobile mule

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
• 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

This page was built for publication: A new bound on maximum independent set and minimum connected dominating set in unit disk graphs