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

被引：23
作者：
Xu, Y [1 ]
机构：
[1] Peking Univ, Dept Comp Sci, Beijing 100871, Peoples R China
[2] City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China
来源：
ALGORITHMICA | 2003年 / 36卷 / 01期
关键词：
gossiping; radio network; deterministic algorithm;
D O I：
10.1007/s00453-002-1010-5
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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(NrootDn + 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.
引用
收藏
页码：93 / 96
页数：4
相关论文
共 5 条
  • [1] Fast broadcasting and gossiping in radio networks
    Chrobak, M
    Gasieniec, L
    Rytter, W
    [J]. 41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, : 575 - 581
  • [2] CHROBAK M, 2001, P 7 ANN INT COMP COM, P483
  • [3] On adaptive deterministic gossiping in ad hoc radio networks
    Gasieniec, L
    Lingas, A
    [J]. INFORMATION PROCESSING LETTERS, 2002, 83 (02) : 89 - 93
  • [4] IODYK P, 2002, P 13 ACM SIAM S DISC, P697
  • [5] Role of heat shock protein 47 on tubulointerstitium in experimental radiation nephropathy
    Liu, D
    Razzaque, MS
    Nazneen, A
    Naito, T
    Taguchi, T
    [J]. PATHOLOGY INTERNATIONAL, 2002, 52 (5-6) : 340 - 347
1