TY - JOUR
T1 - Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks
AU - Du, Hongwei
AU - Ye, Qiang
AU - Zhong, Jiaofei
AU - Wang, Yuexuan
AU - Lee, Wonjun
AU - Park, Haesun
N1 - Funding Information:
This research was jointly supported in part by MEST, Korea under WCU (R33-2008-000-10044-0), by the KOSEF grant funded by the Korea government (MEST) (No. R01-2007-000-11203-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). This research was also supported in part by National Science Foundation of USA under grants CNS0831579 and CCF0728851 and supported in part by the National Basic Research Program of China Grant 2007CB807900, 2007CB807901, the National Natural Science Foundation of China Grant 60604033 and 61100191, by the Hi-Tech Research & Development Program of China Grant 2006AA10Z216, by Shenzhen-Hong Kong Joint Project with Grant No. JSE201007140001A and by Natural Scientific Research Innovation Foundation in Harbin Institute of Technology HIT.NSFIR.2011128.
PY - 2012/8/17
Y1 - 2012/8/17
N2 - 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, mD(u,v)≤α·m(u,v) where α is a constant, mD(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 α<5, this problem has a polynomial-time approximation scheme, that is, for any ε>0, there is a polynomial-time (1+ε)- approximation.
AB - 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, mD(u,v)≤α·m(u,v) where α is a constant, mD(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 α<5, this problem has a polynomial-time approximation scheme, that is, for any ε>0, there is a polynomial-time (1+ε)- approximation.
KW - Minimum connected dominating set
KW - Polynomial-time approximation
KW - Routing cost constraint
KW - Wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=84863324941&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2011.10.010
DO - 10.1016/j.tcs.2011.10.010
M3 - Article
AN - SCOPUS:84863324941
SN - 0304-3975
VL - 447
SP - 38
EP - 43
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -