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 [J].

Chrobak, M ;

Gasieniec, L ;

Rytter, W .

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 [J].

Gasieniec, L ;

Lingas, A .

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 [J].

Liu, D ;

Razzaque, MS ;

Nazneen, A ;

Naito, T ;

Taguchi, T .

PATHOLOGY INTERNATIONAL, 2002, 52 (5-6) :340-347

← 1 →