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 language | English |
---|---|
Pages (from-to) | 451-461 |
Number of pages | 11 |
Journal | Journal of Combinatorial Optimization |
Volume | 23 |
Issue number | 4 |
DOIs | |
Publication status | Published - 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