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

Ling Ding, Xiaofeng Gao, Weili Wu, Wonjun Lee, Xu Zhu, Ding Zhu Du

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

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 languageEnglish
Pages (from-to)297-306
Number of pages10
JournalOptimization Letters
Volume5
Issue number2
DOIs
Publication statusPublished - 2011 May

Keywords

  • CDS
  • Exact algorithm
  • Shortest path

ASJC Scopus subject areas

  • Control and Optimization

Fingerprint

Dive into the research topics of 'An exact algorithm for minimum CDS with shortest path constraint in wireless networks'. Together they form a unique fingerprint.

Cite this