An exact algorithm for minimum CDS with shortest path constraint in wireless networks

An exact algorithm for minimum CDS with shortest path constraint in wireless networks

0.00 Avg rating0 Votes
Article ID: iaor20113739
Volume: 5
Issue: 2
Start Page Number: 297
End Page Number: 306
Publication Date: May 2011
Journal: Optimization Letters
Authors: , , , , ,
Keywords: wireless access networks
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(δ 2 n), where δ is the maximum node degree in communication graph.

Reviews

Required fields are marked *. Your email address will not be published.