@inbook{e4a1e22d60904a6e84a4d81cf0909170,

title = "Time efficient gossiping in known radio networks",

abstract = "We study here the gossiping problem (all-to-all communication) in known radio networks, i.e., when all nodes are aware of the network topology. We start our presentation with a deterministic algorithm for the gossiping problem that works in at most n units of time in any radio network of size n. This is an optimal algorithm in the sense that there exist radio network topologies, such as: a line, a star and a complete graph in which the radio gossiping cannot be completed in less then n units of time. Furthermore, we show that there isn't any radio network topology in which the gossiping task can be solved in time < ⌊log(n - 1)⌋ + 2. We show also that this lower bound can be matched from above for a fraction of all possible integer values of n; and for all other values of n we propose a solution admitting gossiping in time ⌈log(n - 1)⌉ + 2. Finally we study asymptotically optimal O(D)-time gossiping (where D is a diameter of the network) in graphs with max-degree Δ = O(D1-1/(i+1)/ logi n), for any integer constant i ≥ 0 and D large enough.",

author = "Leszek G{\c a}sieniec and Igor Potapov and Qin Xin",

year = "2004",

month = jan,

day = "1",

doi = "10.1007/978-3-540-27796-5_16",

language = "English (US)",

isbn = "3540222308",

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

publisher = "Springer Verlag",

pages = "173--184",

editor = "Rastislav Kralovic and Ondrej Sykora",

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

}