Faster deterministic gossiping in directed ad hoc radio networks

Leszek Ga̧sieniec; Tomasz Radzik; Qin Xin

doi:10.1007/978-3-540-27810-8_34

Faster deterministic gossiping in directed ad hoc radio networks

Leszek Ga̧sieniec, Tomasz Radzik, Qin Xin

Research output: Chapter in Book/Report/Conference proceeding › Chapter

37 Scopus citations

Abstract

We study the gossiping problem in directed ad-hoc radio networks. Our main result is a deterministic algorithm that solves this problem in an n-node network in time O(n^4/3 log⁴ n). The algorithm allows the labels (identifiers) of the nodes to be polynomially large in n, and is based on a novel way of using selective families. The previous best general (i.e., dependent only on n) deterministic upper bounds were O(n^5/3 log³ n) for networks with polynomially large node labels [1], and O(n^3/2 log² n) for networks with linearly large node labels [2,3,4].

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Torben Hagerup, Jyrki Katajainen
Publisher	Springer Verlag
Pages	397-407
Number of pages	11
ISBN (Electronic)	3540223398, 9783540223399
DOIs	https://doi.org/10.1007/978-3-540-27810-8_34
State	Published - 2004
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3111
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-27810-8_34

Cite this

Ga̧sieniec, L., Radzik, T., & Xin, Q. (2004). Faster deterministic gossiping in directed ad hoc radio networks. In T. Hagerup, & J. Katajainen (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 397-407). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3111). Springer Verlag. https://doi.org/10.1007/978-3-540-27810-8_34

Faster deterministic gossiping in directed ad hoc radio networks. / Ga̧sieniec, Leszek; Radzik, Tomasz; Xin, Qin.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Torben Hagerup; Jyrki Katajainen. Springer Verlag, 2004. p. 397-407 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3111).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Ga̧sieniec, L, Radzik, T & Xin, Q 2004, Faster deterministic gossiping in directed ad hoc radio networks. in T Hagerup & J Katajainen (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3111, Springer Verlag, pp. 397-407. https://doi.org/10.1007/978-3-540-27810-8_34

Ga̧sieniec L, Radzik T, Xin Q. Faster deterministic gossiping in directed ad hoc radio networks. In Hagerup T, Katajainen J, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 397-407. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-27810-8_34

Ga̧sieniec, Leszek ; Radzik, Tomasz ; Xin, Qin. / Faster deterministic gossiping in directed ad hoc radio networks. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Torben Hagerup ; Jyrki Katajainen. Springer Verlag, 2004. pp. 397-407 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{c0f402d5888e4de0823a5b6e6edbdb72,

title = "Faster deterministic gossiping in directed ad hoc radio networks",

abstract = "We study the gossiping problem in directed ad-hoc radio networks. Our main result is a deterministic algorithm that solves this problem in an n-node network in time O(n4/3 log4 n). The algorithm allows the labels (identifiers) of the nodes to be polynomially large in n, and is based on a novel way of using selective families. The previous best general (i.e., dependent only on n) deterministic upper bounds were O(n5/3 log3 n) for networks with polynomially large node labels [1], and O(n3/2 log2 n) for networks with linearly large node labels [2,3,4].",

author = "Leszek G{\c a}sieniec and Tomasz Radzik and Qin Xin",

year = "2004",

doi = "10.1007/978-3-540-27810-8_34",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "397--407",

editor = "Torben Hagerup and Jyrki Katajainen",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - Faster deterministic gossiping in directed ad hoc radio networks

AU - Ga̧sieniec, Leszek

AU - Radzik, Tomasz

AU - Xin, Qin

PY - 2004

Y1 - 2004

N2 - We study the gossiping problem in directed ad-hoc radio networks. Our main result is a deterministic algorithm that solves this problem in an n-node network in time O(n4/3 log4 n). The algorithm allows the labels (identifiers) of the nodes to be polynomially large in n, and is based on a novel way of using selective families. The previous best general (i.e., dependent only on n) deterministic upper bounds were O(n5/3 log3 n) for networks with polynomially large node labels [1], and O(n3/2 log2 n) for networks with linearly large node labels [2,3,4].

AB - We study the gossiping problem in directed ad-hoc radio networks. Our main result is a deterministic algorithm that solves this problem in an n-node network in time O(n4/3 log4 n). The algorithm allows the labels (identifiers) of the nodes to be polynomially large in n, and is based on a novel way of using selective families. The previous best general (i.e., dependent only on n) deterministic upper bounds were O(n5/3 log3 n) for networks with polynomially large node labels [1], and O(n3/2 log2 n) for networks with linearly large node labels [2,3,4].

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

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

U2 - 10.1007/978-3-540-27810-8_34

DO - 10.1007/978-3-540-27810-8_34

M3 - Chapter

AN - SCOPUS:35048874747

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 397

EP - 407

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Hagerup, Torben

A2 - Katajainen, Jyrki

PB - Springer Verlag

ER -

Faster deterministic gossiping in directed ad hoc radio networks

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this