Article ID: | iaor20113739 |
Volume: | 5 |
Issue: | 2 |
Start Page Number: | 297 |
End Page Number: | 306 |
Publication Date: | May 2011 |
Journal: | Optimization Letters |
Authors: | Du Ding-Zhu, Wu Weili, Zhu Xu, Lee Wonjun, Ding Ling, Gao Xiaofeng |
Keywords: | wireless access networks |
In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be included. Such a minimum CDS (we name this problem as SPCDS) is an important tache of some other algorithms for constructing a minimum CDS. We prove that finding such a minimum SPCDS can be achieved in polynomial time and design an exact algorithm with time complexity