Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks
- Authors
- Du, Hongwei; Ye, Qiang; Zhong, Jiaofei; Wang, Yuexuan; Lee, Wonjun; Park, Haesun
- Issue Date
- 17-8월-2012
- Publisher
- ELSEVIER SCIENCE BV
- Keywords
- Polynomial-time approximation; Minimum connected dominating set; Routing cost constraint; Wireless sensor networks
- Citation
- THEORETICAL COMPUTER SCIENCE, v.447, pp.38 - 43
- Indexed
- SCIE
SCOPUS
- Journal Title
- THEORETICAL COMPUTER SCIENCE
- Volume
- 447
- Start Page
- 38
- End Page
- 43
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/107690
- DOI
- 10.1016/j.tcs.2011.10.010
- ISSN
- 0304-3975
- Abstract
- To reduce routing cost in wireless sensor networks, we study a problem of minimizing the size of connected dominating set D under constraint that for any two nodes u and v, m(D)(u, v) <= alpha.m(u, v) where alpha is a constant, m(D)(u, v) is the number of intermediate nodes on a shortest path connecting u and v through D and m(u, v) is the number of intermediate nodes in a shortest path between u and v in a given unit disk graph. We show that for alpha >= 5, this problem has a polynomial-time approximation scheme, that is, for any epsilon > 0, there is a polynomial-time (1 + epsilon)-approximation. (c) 2011 Elsevier B.V. All rights reserved.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - School of Cyber Security > Department of Information Security > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.