Detailed Information
Cited 0 time in 
Cited 0 time in 
Cited 0 time in
Metadata Downloads
An exact algorithm for minimum CDS with shortest path constraint in wireless networks
- Authors
- Ding, Ling; Gao, Xiaofeng; Wu, Weili; Lee, Wonjun; Zhu, Xu; Du, Ding-Zhu
- Issue Date
- May-2011
- Publisher
- SPRINGER HEIDELBERG
- Keywords
- CDS; Shortest path; Exact algorithm
- Citation
- OPTIMIZATION LETTERS, v.5, no.2, pp 297 - 306
- Pages
- 10
- Indexed
- SCIE
SCOPUS
- Journal Title
- OPTIMIZATION LETTERS
- Volume
- 5
- Number
- 2
- Start Page
- 297
- End Page
- 306
- ISSN
- 1862-4472
1862-4480
- Abstract
- 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 O(delta (2) n), where delta is the maximum node degree in communication graph.
- Files in This Item
- There are no files associated with this item.
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
Related Researcher
- Lee, Won jun
- Department of Information Security