PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings
Pages252-259
Number of pages8
EditionPART 1
DOIs
Publication statusPublished - 2010
Event4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010 - Kailua-Kona, HI, United States
Duration: 2010 Dec 182010 Dec 20

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6508 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010
Country/TerritoryUnited States
CityKailua-Kona, HI
Period10/12/1810/12/20

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 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.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks'. Together they form a unique fingerprint.

Cite this