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

doi:10.1007/s11590-010-0208-8

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 journal › Article › peer-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(δ²n), 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	https://doi.org/10.1007/s11590-010-0208-8
Publication status	Published - 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

Access to Document

10.1007/s11590-010-0208-8

Cite this

@article{b13f666d1efa4a45a5b7ec3b8d255db3,

title = "An exact algorithm for minimum CDS with shortest path constraint in wireless 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(δ2n), where δ is the maximum node degree in communication graph.",

keywords = "CDS, Exact algorithm, Shortest path",

author = "Ling Ding and Xiaofeng Gao and Weili Wu and Wonjun Lee and Xu Zhu and Du, {Ding Zhu}",

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).",

year = "2011",

month = may,

doi = "10.1007/s11590-010-0208-8",

language = "English",

volume = "5",

pages = "297--306",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

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

AU - Ding, Ling

AU - Gao, Xiaofeng

AU - Wu, Weili

AU - Lee, Wonjun

AU - Zhu, Xu

AU - Du, Ding Zhu

N1 - 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).

PY - 2011/5

Y1 - 2011/5

N2 - 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.

AB - 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.

KW - CDS

KW - Exact algorithm

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=79952902539&partnerID=8YFLogxK

U2 - 10.1007/s11590-010-0208-8

DO - 10.1007/s11590-010-0208-8

M3 - Article

AN - SCOPUS:79952902539

SN - 1862-4472

VL - 5

SP - 297

EP - 306

JO - Optimization Letters

JF - Optimization Letters

IS - 2

ER -

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

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this