Polynomial time approximation scheme for t-latency bounded information propagation problem in wireless networks

Wei Zhang, Zhao Zhang, Wei Wang, Feng Zou, Wonjun Lee

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

Latency of information propagating in wireless network is gaining more and more attention recently. This paper studies the problem of t-Latency Bounded Information Propagation (t-LBIP) problem in wireless networks which are represented by unit-disk graphs. So far, no guaranteed approximation algorithm has been achieved for t-LBIP when t ≥ 2. In this paper, we propose a Polynomial Time Approximation Scheme for t-LBIP under the condition that the maximum degree is bounded by a constant.

Original languageEnglish
Pages (from-to)451-461
Number of pages11
JournalJournal of Combinatorial Optimization
Volume23
Issue number4
DOIs
Publication statusPublished - 2012 May

Bibliographical note

Funding Information:
Acknowledgements This research was supported by NSFC (10971255), the Key Project of Chinese Ministry of Education (208161), Program for New Century Excellent Talents in University, the Project-sponsored by SRF for ROCS, SEM, and National Science Foundation of China Grant No. 11071191. It was jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), a NRF Grant under (KRF-2008-314-D00354), and MKE, Korea under ITRC NIPA-2010-(C1090-1021-0008).

Keywords

  • Information propagation
  • Polynomial time approximation scheme
  • Unit disk graph
  • Wireless network

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Polynomial time approximation scheme for t-latency bounded information propagation problem in wireless networks'. Together they form a unique fingerprint.

Cite this