A randomized algorithm for gossiping in radio networks

Marek Chrobak; Leszek Gąsieniec; Wojciech Rytter

doi:10.1007/3-540-44679-6_54

A randomized algorithm for gossiping in radio networks

Marek Chrobak, Leszek Gąsieniec, Wojciech Rytter

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

27 Scopus citations

Abstract

We present an O(n log⁴ n)-time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O(n^3/2 log² n).

Original language	English (US)
Title of host publication	Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings
Editors	Jie Wang
Publisher	Springer Verlag
Pages	483-492
Number of pages	10
ISBN (Print)	9783540424949
DOIs	https://doi.org/10.1007/3-540-44679-6_54
State	Published - 2001
Externally published	Yes
Event	7th Annual International Conference on Computing and Combinatorics, COCOON 2001 - Guilin, China Duration: Aug 20 2001 → Aug 23 2001

Publication series

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

Conference

Conference	7th Annual International Conference on Computing and Combinatorics, COCOON 2001
Country/Territory	China
City	Guilin
Period	8/20/01 → 8/23/01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-44679-6_54

Cite this

Chrobak, M., Gąsieniec, L., & Rytter, W. (2001). A randomized algorithm for gossiping in radio networks. In J. Wang (Ed.), Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings (pp. 483-492). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108). Springer Verlag. https://doi.org/10.1007/3-540-44679-6_54

A randomized algorithm for gossiping in radio networks. / Chrobak, Marek; Gąsieniec, Leszek; Rytter, Wojciech.
Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. ed. / Jie Wang. Springer Verlag, 2001. p. 483-492 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108).

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

Chrobak, M, Gąsieniec, L & Rytter, W 2001, A randomized algorithm for gossiping in radio networks. in J Wang (ed.), Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2108, Springer Verlag, pp. 483-492, 7th Annual International Conference on Computing and Combinatorics, COCOON 2001, Guilin, China, 8/20/01. https://doi.org/10.1007/3-540-44679-6_54

Chrobak M, Gąsieniec L, Rytter W. A randomized algorithm for gossiping in radio networks. In Wang J, editor, Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. Springer Verlag. 2001. p. 483-492. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44679-6_54

Chrobak, Marek ; Gąsieniec, Leszek ; Rytter, Wojciech. / A randomized algorithm for gossiping in radio networks. Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. editor / Jie Wang. Springer Verlag, 2001. pp. 483-492 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{86cce86cabd0471abe1ae189669381a0,

title = "A randomized algorithm for gossiping in radio networks",

abstract = "We present an O(n log4 n)-time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O(n3/2 log2 n).",

author = "Marek Chrobak and Leszek G{\c a}sieniec and Wojciech Rytter",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 7th Annual International Conference on Computing and Combinatorics, COCOON 2001 ; Conference date: 20-08-2001 Through 23-08-2001",

year = "2001",

doi = "10.1007/3-540-44679-6_54",

language = "English (US)",

isbn = "9783540424949",

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

publisher = "Springer Verlag",

pages = "483--492",

editor = "Jie Wang",

booktitle = "Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings",

}

TY - GEN

T1 - A randomized algorithm for gossiping in radio networks

AU - Chrobak, Marek

AU - Gąsieniec, Leszek

AU - Rytter, Wojciech

PY - 2001

Y1 - 2001

N2 - We present an O(n log4 n)-time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O(n3/2 log2 n).

AB - We present an O(n log4 n)-time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O(n3/2 log2 n).

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

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

U2 - 10.1007/3-540-44679-6_54

DO - 10.1007/3-540-44679-6_54

M3 - Conference contribution

AN - SCOPUS:84944049102

SN - 9783540424949

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

SP - 483

EP - 492

BT - Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings

A2 - Wang, Jie

PB - Springer Verlag

T2 - 7th Annual International Conference on Computing and Combinatorics, COCOON 2001

Y2 - 20 August 2001 through 23 August 2001

ER -

A randomized algorithm for gossiping in radio networks

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this