Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks

DOI10.1016/j.tcs.2011.10.010zbMath1243.68054OpenAlexW1987818736MaRDI QIDQ443711

Qiang Ye, Yuexuan Wang, Jiaofei Zhong, Haesun Park, Won Jun Lee, Hongwei David Du

Publication date: 13 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.10.010

zbMATH Keywords

polynomial-time approximationwireless sensor networksminimum connected dominating setrouting cost constraint

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)

Related Items (3)

The connected domination number of grids ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs

Cites Work

• Unnamed Item
• A greedy approximation for minimum connected dominating sets
• Approximation algorithms for connected dominating sets
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS

This page was built for publication: Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks