کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652398 | 1632597 | 2009 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting](/preview/png/4652398.png)
چکیده انگلیسی
In this paper, we provide a detailed comparison between a fully randomized protocol for rumour spreading on a complete graph and a quasirandom protocol introduced by Doerr, Friedrich and Sauerwald [Doerr, B., T. Friedrich and T. Sauerwald, Quasirandom broadcasting, In Proceedings of the 19th Annual ACM-SIAM Symp. on Disc. Alg. (SODA), pp. 773-781, 2008]. In the former, initially there is one vertex which holds a piece of information and during each round every one of the informed vertices chooses one of its neighbours uniformly at random, independently of every other vertex, and informs it. In the quasirandom version of this method (see Doerr et al. [Doerr, B., T. Friedrich and T. Sauerwald, Quasirandom broadcasting, In Proceedings of the 19th Annual ACM-SIAM Symp. on Disc. Alg. (SODA), pp. 773-781, 2008]) each vertex is equipped with a cyclic ordering of its neighbours. Once a vertex is informed, it chooses uniformly at random only the first neighbour it will inform and at each subsequent round it informs the successor in its cyclic ordering. The randomized protocol was analyzed by Frieze and Grimmett [Frieze, A.M., and G.R. Grimmett, The shortest-path problem for graphs with random arc-lengths, Discrete Appl. Math. 10 (1985), 57-77] and their analysis was refined by Pittel [Pittel, B., On spreading a rumor, SIAM J. Appl. Math. 47 (1987), 213-223], who gave a precise description of its evolution. In the present work, we present a precise analysis of the evolution of the quasirandom protocol on the complete graph with n vertices and show that it evolves essentially in the same way as the randomized protocol. In particular, if S(n) denotes the number of rounds that are needed until all vertices are informed, we show that for any slowly growing function Ï(n) with probability 1âo(1) we havelog2n+lnnâ4lnlnn⩽S(n)⩽log2n+lnn+Ï(n).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 34, 1 August 2009, Pages 553-559
Journal: Electronic Notes in Discrete Mathematics - Volume 34, 1 August 2009, Pages 553-559
نویسندگان
Anna Huber, Nikolaos Fountoulakis,