Skip to search boxSkip to navigationSkip to main content

A Randomized Algorithm for Gossiping in Radio Networks

  • Marek Chrobak(corresponding author)
    ,
  • Leszek Ga̧sieniec
    ,
  • Wojciech Rytter
*Corresponding author for this work
  • University of California at Riverside
    ,
  • University of Liverpool
    ,
  • University of Warsaw
Scholary Output:
Contribution to journal
Article
 Peer-review

Open access

Abstract

We present an O(n log 4n)-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/2log 2n).

Publication Information

Output type

Scholary Output:
Contribution to journal
Article
 Peer-review

Original language

English (US)

Pages from-to (Number of pages)

Pages 119-124 (6 pages)

Journal (Volume, Issue Number)

Networks (Volume 43, Issue 2)

Publication milestones

  • Published - 03/2004

Publication status

Published - 03/2004

ISSN

0028-3045

Publication IDs

  • Scopus: 2042515611

Access to documents

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
0.75
SciVal
Author count
3
SciVal
citations
14
SciVal
Paper percentile
64
Scopus
citations
15, opens in new tab

PlumX, opens in new tab

Citation count
16
Captures
5