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