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

Lidong Wu (), Hongwei Du (), Weili Wu (), Yuqing Zhu (), Ailan Wang () and Wonjun Lee ()
Additional contact information
Lidong Wu: University of Texas at Dallas
Hongwei Du: Harbin Institute of Technology, Shenzhen Graduate School
Weili Wu: University of Texas at Dallas
Yuqing Zhu: University of Texas at Dallas
Ailan Wang: Taiyuan University of Technology
Wonjun Lee: Korea University

Journal of Combinatorial Optimization, 2015, vol. 30, issue 1, No 2, 18-26

Abstract: 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 $$\alpha $$ α ROC–CDS where $$\alpha \ge 5$$ α ≥ 5 , that is, there exists a polynomial-time $$(1+\varepsilon )$$ ( 1 + ε ) -approximation for minimum CDS under constraint that for every pair of nodes u and v, $$m_{CDS}(u,v) \le m(u,v)$$ m CDS ( u , v ) ≤ m ( u , v ) where $$m(u,v)$$ m ( u , v ) denotes the number of intermediate nodes in the shortest path between u and v, and $$m_{CDS}(u,v)$$ 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.

Keywords: Growth bounded graphs; Minimum connected dominating set; Routing cost constraint; Algorithm PTAS (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9626-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:1:d:10.1007_s10878-013-9626-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9626-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().