A randomized algorithm for gossiping in radio networks
- Marek Chrobak,
- Leszek Gąsieniec,
- Wojciech Rytter
- University of California at Riverside,
- University of Liverpool,
- University of Warsaw
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Related Event
Title
7th Annual International Conference on Computing and Combinatorics, COCOON 2001
Event type
ConferenceDate
08/20/2001 - 08/23/2001Location
GuilinChina
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).
Publication Information
Output type
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Original language
English (US)Pages from-to (Number of pages)
Pages 483-492 (10 pages)Publication milestones
- Published - 2001
Publication status
Published - 2001
Publisher
Springer VerlagPublication series
- Publication series name: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print): 0302-9743
ISSN (Electronic): 1611-3349
Volume: 2108
ISBN (Print)
9783540424949Publication IDs
- Scopus: 84944049102
Host publication title
Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, ProceedingsHost publication editors
- Jie Wang
Publication metrics
Metrics
Fractional count
1
Fractional count
0.33
Fractional count
2
Fractional count
0.67
Fractional count
1
Fractional count
1
SciVal
FWCI
3.79
SciVal
Author count
3
SciVal
citations
26
SciVal
Paper percentile
75
PlumX, opens in new tab
Citation count
25
Captures
3