Premium
Rumor spreading in random evolving graphs
Author(s) -
Clementi Andrea,
Crescenzi Pierluigi,
Doerr Carola,
Fraigniaud Pierre,
Pasquale Francesco,
Silvestri Riccardo
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20586
Subject(s) - logarithm , rumor , random graph , enhanced data rates for gsm evolution , computer science , markov process , range (aeronautics) , mathematics , discrete mathematics , theoretical computer science , graph , statistics , telecommunications , engineering , mathematical analysis , public relations , political science , aerospace engineering
Abstract We analyze randomized broadcast in dynamic networks modeled as edge‐Markovian evolving graphs. The most realistic range of edge‐Markovian parameters yields sparse and disconnected graphs. We prove that, in this setting, the “push” protocol completes with high probability in optimal logarithmic time. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 290–312, 2016