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

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

doi:10.1007/s10878-010-9359-x

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 journal › Article › peer-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 language	English
Pages (from-to)	451-461
Number of pages	11
Journal	Journal of Combinatorial Optimization
Volume	23
Issue number	4
DOIs	https://doi.org/10.1007/s10878-010-9359-x
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

Access to Document

10.1007/s10878-010-9359-x

Cite this

@article{5fda9bcd14e34654bef2209c6b8306b4,

title = "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 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.",

keywords = "Information propagation, Polynomial time approximation scheme, Unit disk graph, Wireless network",

author = "Wei Zhang and Zhao Zhang and Wei Wang and Feng Zou and Wonjun Lee",

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).",

year = "2012",

month = may,

doi = "10.1007/s10878-010-9359-x",

language = "English",

volume = "23",

pages = "451--461",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

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

AU - Zhang, Wei

AU - Zhang, Zhao

AU - Wang, Wei

AU - Zou, Feng

AU - Lee, Wonjun

N1 - 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).

PY - 2012/5

Y1 - 2012/5

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

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

KW - Information propagation

KW - Polynomial time approximation scheme

KW - Unit disk graph

KW - Wireless network

UR - http://www.scopus.com/inward/record.url?scp=84863722854&partnerID=8YFLogxK

U2 - 10.1007/s10878-010-9359-x

DO - 10.1007/s10878-010-9359-x

M3 - Article

AN - SCOPUS:84863722854

SN - 1382-6905

VL - 23

SP - 451

EP - 461

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

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

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this