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 Library locked




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

Journal Title*:

SIAM Journal on Discrete Mathematics

Journal's URL:

http://scitation.aip.org/journals/doc/SIAMDL-home/jrnls/top.jsp?key=SJDMEC

Download URL
for the article:

http://link.aip.org/link/?SJD/23/1964/1

Language:

English

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, Abstract, ©

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},
}


Entry last modified by Manuel Lamotte-Schubert, 03/28/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/14/2010 05:02:47 PM
Revisions
2.
1.
0.

Editor(s)
Manuel Lamotte-Schubert
Anja Becker
Anna Huber

Edit Dates
28.03.2011 10:54:57
08.03.2010 13:26:41
02/14/2010 05:02:47 PM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section