PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs

Lidong Wu; Hongwei Du; Weili Wu; Yuqing Zhu; Ailan Wang; Wonjun Lee

doi:10.1007/s10878-013-9626-8

PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs

Lidong Wu, Hongwei Du, Weili Wu, Yuqing Zhu, Ailan Wang, Wonjun Lee

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

Abstract

Connected dominating set (CDS) has played an important role in building virtual backbone, which is used on unicast, multicast, and fault-tolerant routing in wireless sensor networks. In order to reduce traffic congestion and communication delay, a routing-cost constrained minimum CDS (ROC–CDS) has been studied extensively in the literature. In this paper, we present a PTAS for αROC–CDS where α≥5, that is, there exists a polynomial-time (1+ε)-approximation for minimum CDS under constraint that for every pair of nodes u and v, m_CDS(u,v)≤m(u,v) where m(u,v) denotes the number of intermediate nodes in the shortest path between u and v, and m_CDS(u,v) denotes the number of intermediate nodes of the shortest path between u and v through CDS produced by the approximation algorithm.

Original language	English
Pages (from-to)	18-26
Number of pages	9
Journal	Journal of Combinatorial Optimization
Volume	30
Issue number	1
DOIs	https://doi.org/10.1007/s10878-013-9626-8
Publication status	Published - 2015 Jul 28

Bibliographical note

Funding Information:
This work was supported by National Natural Science Foundation of China with Grants 61100191 and 11071271, and Shenzhen Strategic Emerging Industries Program with Grants No. ZDSY20120613125016389 and No. JCYJ20120613151201451, and Natural Scientific Research Innovation Foundation of Harbin Institute of Technology under Project 2011128. This work was also supported in part by National Science Foundation of USA under Grants CNS101630 and CCF0829993. This research was also jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), MEST, Korea under Basic Science Research Program (2011-0012216), and MKE, Korea under ITRC NIPA-2011-(C1090-1121-0008).

Publisher Copyright:
© 2013, Springer Science+Business Media New York.

Keywords

Algorithm PTAS
Growth bounded graphs
Minimum connected dominating set
Routing cost constraint

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/s10878-013-9626-8

Cite this

@article{30545531b95348ce997bc7be9a27f616,

title = "PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs",

abstract = "Connected dominating set (CDS) has played an important role in building virtual backbone, which is used on unicast, multicast, and fault-tolerant routing in wireless sensor networks. In order to reduce traffic congestion and communication delay, a routing-cost constrained minimum CDS (ROC–CDS) has been studied extensively in the literature. In this paper, we present a PTAS for αROC–CDS where α≥5, that is, there exists a polynomial-time (1+ε)-approximation for minimum CDS under constraint that for every pair of nodes u and v, mCDS(u,v)≤m(u,v) where m(u,v) denotes the number of intermediate nodes in the shortest path between u and v, and mCDS(u,v) denotes the number of intermediate nodes of the shortest path between u and v through CDS produced by the approximation algorithm.",

keywords = "Algorithm PTAS, Growth bounded graphs, Minimum connected dominating set, Routing cost constraint",

author = "Lidong Wu and Hongwei Du and Weili Wu and Yuqing Zhu and Ailan Wang and Wonjun Lee",

note = "Funding Information: This work was supported by National Natural Science Foundation of China with Grants 61100191 and 11071271, and Shenzhen Strategic Emerging Industries Program with Grants No. ZDSY20120613125016389 and No. JCYJ20120613151201451, and Natural Scientific Research Innovation Foundation of Harbin Institute of Technology under Project 2011128. This work was also supported in part by National Science Foundation of USA under Grants CNS101630 and CCF0829993. This research was also jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), MEST, Korea under Basic Science Research Program (2011-0012216), and MKE, Korea under ITRC NIPA-2011-(C1090-1121-0008). Publisher Copyright: {\textcopyright} 2013, Springer Science+Business Media New York.",

year = "2015",

month = jul,

day = "28",

doi = "10.1007/s10878-013-9626-8",

language = "English",

volume = "30",

pages = "18--26",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs

AU - Wu, Lidong

AU - Du, Hongwei

AU - Wu, Weili

AU - Zhu, Yuqing

AU - Wang, Ailan

AU - Lee, Wonjun

N1 - Funding Information: This work was supported by National Natural Science Foundation of China with Grants 61100191 and 11071271, and Shenzhen Strategic Emerging Industries Program with Grants No. ZDSY20120613125016389 and No. JCYJ20120613151201451, and Natural Scientific Research Innovation Foundation of Harbin Institute of Technology under Project 2011128. This work was also supported in part by National Science Foundation of USA under Grants CNS101630 and CCF0829993. This research was also jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), MEST, Korea under Basic Science Research Program (2011-0012216), and MKE, Korea under ITRC NIPA-2011-(C1090-1121-0008). Publisher Copyright: © 2013, Springer Science+Business Media New York.

PY - 2015/7/28

Y1 - 2015/7/28

N2 - Connected dominating set (CDS) has played an important role in building virtual backbone, which is used on unicast, multicast, and fault-tolerant routing in wireless sensor networks. In order to reduce traffic congestion and communication delay, a routing-cost constrained minimum CDS (ROC–CDS) has been studied extensively in the literature. In this paper, we present a PTAS for αROC–CDS where α≥5, that is, there exists a polynomial-time (1+ε)-approximation for minimum CDS under constraint that for every pair of nodes u and v, mCDS(u,v)≤m(u,v) where m(u,v) denotes the number of intermediate nodes in the shortest path between u and v, and mCDS(u,v) denotes the number of intermediate nodes of the shortest path between u and v through CDS produced by the approximation algorithm.

AB - Connected dominating set (CDS) has played an important role in building virtual backbone, which is used on unicast, multicast, and fault-tolerant routing in wireless sensor networks. In order to reduce traffic congestion and communication delay, a routing-cost constrained minimum CDS (ROC–CDS) has been studied extensively in the literature. In this paper, we present a PTAS for αROC–CDS where α≥5, that is, there exists a polynomial-time (1+ε)-approximation for minimum CDS under constraint that for every pair of nodes u and v, mCDS(u,v)≤m(u,v) where m(u,v) denotes the number of intermediate nodes in the shortest path between u and v, and mCDS(u,v) denotes the number of intermediate nodes of the shortest path between u and v through CDS produced by the approximation algorithm.

KW - Algorithm PTAS

KW - Growth bounded graphs

KW - Minimum connected dominating set

KW - Routing cost constraint

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

U2 - 10.1007/s10878-013-9626-8

DO - 10.1007/s10878-013-9626-8

M3 - Article

AN - SCOPUS:84938213624

SN - 1382-6905

VL - 30

SP - 18

EP - 26

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this