A Randomized Algorithm for Gossiping in Radio Networks
作者： Marek Chrobak , Leszek Gąsieniec , Wojciech Rytter
关键词:
摘要: We present an O(n log4n)-time randomized algorithm for gossiping in radio networks with unknown topology. This is the first this model whose running time only a poly-logarithmic factor away from optimum. The fastest previously known (deterministic) problem works O(n3/2 log2 n).
springer.com
elsevier.com
mimuw.edu.pl 参考文章(32)
Reuven Bar-Yehuda, Amos Israeli, Alon Itai, Multiple Communication in Multihop Radio Networks SIAM Journal on Computing. ,vol. 22, pp. 875- 887 ,(1993) , 10.1137/0222055
D. Krizanc, A. Pelc, E. Kranakis, Fault-tolerant broadcasting in radio networks Lecture Notes in Computer Science. pp. 283- 294 ,(1998)
Allen Pahlavan, K, and Levesque, Wireless Information Networks ,(1995)
Krzysztof Diks, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, The Impact of Knowledge on Broadcasting Time in Radio Networks european symposium on algorithms. pp. 41- 52 ,(1999) , 10.1007/3-540-48481-7_5
Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract) european symposium on algorithms. pp. 283- 294 ,(1998) , 10.1007/3-540-68530-8_24
KRISHNAMURTHI RAVISHANKAR, SURESH SINGH, GOSSIPING ON A RING WITH RADIOS Parallel Processing Letters. ,vol. 6, pp. 115- 126 ,(1996) , 10.1142/S0129626496000121
Eyal Kushilevitz, Yishay Mansour, Computation in noisy radio networks symposium on discrete algorithms. pp. 236- 243 ,(1998) , 10.5555/314613.314709
Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg, Single round simulation on radio networks Journal of Algorithms. ,vol. 13, pp. 188- 210 ,(1992) , 10.1016/0196-6774(92)90015-5
Leszek Gąsieniec, Wojciech Rytter, Bogdan S. Chlebus, Andrzej Pelc, Alan Gibbons, Deterministic broadcasting in unknown radio networks symposium on discrete algorithms. pp. 861- 870 ,(2000) , 10.5555/338219.338652
Gianluca De Marco, Andrzej Pelc, Faster broadcasting in unknown radio networks Information Processing Letters. ,vol. 79, pp. 53- 56 ,(2001) , 10.1016/S0020-0190(00)00178-2