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(δ2n), where δ is the maximum node degree in communication graph.
Original language | English |
---|---|
Pages (from-to) | 297-306 |
Number of pages | 10 |
Journal | Optimization Letters |
Volume | 5 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2011 May |
Keywords
- CDS
- Exact algorithm
- Shortest path
ASJC Scopus subject areas
- Control and Optimization