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

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 ta parts per thousand yen2. 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.