An O(n1.5) deterministic gossiping algorithm for radio networks

Ying Xu

doi:10.1007/s00453-002-1010-5

An O(n^1.5) deterministic gossiping algorithm for radio networks

Ying Xu

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

31 Citations (Scopus)

Abstract

We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D, we present an adaptive deterministic gossiping algorithm of time O(√Dn + n log² n) or O(n^1.5). This algorithm is a tuned version of the fastest previously known gossiping algorithm due to Gasieniec and Lingas [1], and improves the time complexity by a poly-logarithmic factor.
© 2003 Springer-Verlag New York Inc.

Original language	English
Pages (from-to)	93-96
Journal	Algorithmica (New York)
Volume	36
Issue number	1
DOIs	https://doi.org/10.1007/s00453-002-1010-5
Publication status	Published - May 2003
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

This research was supported by CERG Grant [CityU1070/02E] of Hong Kong.

Research Keywords

Deterministic algorithm
Gossiping
Radio network

RGC Funding Information

RGC-funded

Access Output

10.1007/s00453-002-1010-5

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{eaffbb470be247149bf6b1b1dd779a61,

title = "An O(n1.5) deterministic gossiping algorithm for radio networks",

abstract = "We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D, we present an adaptive deterministic gossiping algorithm of time O(√Dn + n log2 n) or O(n1.5). This algorithm is a tuned version of the fastest previously known gossiping algorithm due to Gasieniec and Lingas [1], and improves the time complexity by a poly-logarithmic factor. {\textcopyright} 2003 Springer-Verlag New York Inc.",

keywords = "Deterministic algorithm, Gossiping, Radio network",

author = "Ying Xu",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2003",

month = may,

doi = "10.1007/s00453-002-1010-5",

language = "English",

volume = "36",

pages = "93--96",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - An O(n1.5) deterministic gossiping algorithm for radio networks

AU - Xu, Ying

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2003/5

Y1 - 2003/5

N2 - We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D, we present an adaptive deterministic gossiping algorithm of time O(√Dn + n log2 n) or O(n1.5). This algorithm is a tuned version of the fastest previously known gossiping algorithm due to Gasieniec and Lingas [1], and improves the time complexity by a poly-logarithmic factor. © 2003 Springer-Verlag New York Inc.

AB - We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D, we present an adaptive deterministic gossiping algorithm of time O(√Dn + n log2 n) or O(n1.5). This algorithm is a tuned version of the fastest previously known gossiping algorithm due to Gasieniec and Lingas [1], and improves the time complexity by a poly-logarithmic factor. © 2003 Springer-Verlag New York Inc.

KW - Deterministic algorithm

KW - Gossiping

KW - Radio network

UR - https://www.scopus.com/pages/publications/0345656721

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0345656721&origin=recordpage

U2 - 10.1007/s00453-002-1010-5

DO - 10.1007/s00453-002-1010-5

M3 - RGC 21 - Publication in refereed journal

SN - 0178-4617

VL - 36

SP - 93

EP - 96

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 1

ER -