TY - GEN
T1 - PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks
AU - Du, Hongwei
AU - Ye, Qiang
AU - Zhong, Jioafei
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 the Hi-Tech Research & Development Program of China Grant 2006AA10Z216.
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 the Hi-Tech Research & Development Program of China Grant 2006AA10Z216.
PY - 2010
Y1 - 2010
N2 - To reduce routing cost and to improve road load balance, we study a problem of minimizing size of connected dominating set D under constraint that for any two nodes u and v, the routing cost through D is within a factor of α from the minimum, the cost of the shortest path between u and v. We show that for α ≥ 5, this problem in unit disk graphs has a polynomial-time approximation scheme, that is, for any ε > 0, there is a polynomial-time (1 + ε)-approximation.
AB - To reduce routing cost and to improve road load balance, we study a problem of minimizing size of connected dominating set D under constraint that for any two nodes u and v, the routing cost through D is within a factor of α from the minimum, the cost of the shortest path between u and v. We show that for α ≥ 5, this problem in unit disk graphs has a polynomial-time approximation scheme, that is, for any ε > 0, there is a polynomial-time (1 + ε)-approximation.
UR - http://www.scopus.com/inward/record.url?scp=78650831952&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-17458-2_21
DO - 10.1007/978-3-642-17458-2_21
M3 - Conference contribution
AN - SCOPUS:78650831952
SN - 3642174574
SN - 9783642174575
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 252
EP - 259
BT - Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings
T2 - 4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010
Y2 - 18 December 2010 through 20 December 2010
ER -