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

    Bibliographical note

    Funding Information:
    Acknowledgments This research was supported by National Science Foundation of USA under Grant CNS0831579 and CCF0728851. This research was also jointly supported by MEST, Korea under WCU (R33-2008-000-10044-0), by KRF Grant funded by (KRF-2008-314-D00354), and by MKE, Korea under ITRC IITA-2009-(C1090-0902-0046) and IITA-2009-(C1090-0902-0007).

    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