Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor(s)
 Author(s): Fountoulakis, Nikolaos Huber, Anna dblp dblp
 BibTeX cite key*: HF2009

 Title
 Title*: Quasirandom rumor spreading on the complete graph is as fast as randomized rumor spreading

 Journal

 Publisher
 Publisher's Name: Publisher's URL: Publisher's Address: ISSN:

 Vol, No, pp, Date
 Volume*: 23 Number: 4 Publishing Date: 2009 Pages*: 1964-1991 Number of VG Pages: Page Start: Page End: Sequence Number: DOI: 10.1137/09075768X

 Note: (LaTeX) Abstract: 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 (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 and independently and informs it. In the quasirandom version of this method (cf. Doerr et al.) each vertex has a cyclic list of its neighbours. Once a vertex has been informed, it chooses uniformly at random only one neighbour. In the following round, it informs this neighbour and at each subsequent round it picks the next neighbour from its list and informs it. We give 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 $\omega (n)$ $$\log_2 n + \ln n - 4\ln \ln n \leq S(n) \leq \log_2 n + \ln n + \omega (n),$$ with probability $1-o(1)$. URL for the Abstract: Categories, Keywords: HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{HF2009,
AUTHOR = {Fountoulakis, Nikolaos and Huber, Anna},
TITLE = {Quasirandom rumor spreading on the complete graph is as fast as randomized rumor spreading},
JOURNAL = {SIAM Journal on Discrete Mathematics},
YEAR = {2009},
NUMBER = {4},
VOLUME = {23},
PAGES = {1964--1991},
DOI = {10.1137/09075768X},
}