Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks

Hongwei Du, Qiang Ye, Jiaofei Zhong, Yuexuan Wang, Wonjun Lee, Haesun Park

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


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 languageEnglish
Pages (from-to)38-43
Number of pages6
JournalTheoretical Computer Science
Publication statusPublished - 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.


  • Minimum connected dominating set
  • Polynomial-time approximation
  • Routing cost constraint
  • Wireless sensor networks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks'. Together they form a unique fingerprint.

Cite this