An O ( n 1.5 ) Deterministic Gossiping Algorithm for Radio Networks |
| |
| Authors: | Ying Xu |
| |
| Affiliation: | (1) Department of Computer Science, Peking University, Beijing 100871, People's Republic of China and Department of Computer Science, City University, Tat Chee Road, Kowloon, Hong Kong. xuying@cs.cityu.edu.hk., HK |
| |
| Abstract: |
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 ( n+n log
2
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. |
| |
| Keywords: | , Gossiping, Radio network, Deterministic algorithm, |
| 本文献已被 SpringerLink 等数据库收录！ |
|
