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