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, 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.
| Original language | English |
|---|---|
| Pages (from-to) | 38-43 |
| Number of pages | 6 |
| Journal | Theoretical Computer Science |
| Volume | 447 |
| DOIs | |
| Publication status | Published - 2012 Aug 17 |
Bibliographical note
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.
Keywords
- Minimum connected dominating set
- Polynomial-time approximation
- Routing cost constraint
- Wireless sensor networks
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science