Flooding in dynamic graphs with arbitrary degree sequence

Abstract : This paper addresses the flooding problem in dynamic graphs, where flooding is the basic mechanism in which every node becoming aware of a piece of information at step tt forwards this information to all its neighbors at all forthcoming steps t′>tt′>t. We show that a technique developed in a previous paper, for analyzing flooding in a Markovian sequence of Erdös–Rényi graphs, is robust enough to be used also in different contexts. We establish this fact by analyzing flooding in a sequence of graphs drawn independently at random according to a model of random graphs with given expected degree sequence. In the prominent case of power-law degree distributions, we prove that flooding takes almost surely O(logn)O(logn) steps even if, almost surely, none of the graphs in the sequence is connected. In the general case of graphs with an arbitrary degree sequence, we prove several upper bounds on the flooding time, which depend on specific properties of the degree sequence.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2014, 74 (5), pp.2433-2437. 〈10.1016/j.jpdc.2014.01.007〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01102106
Contributeur : Pierre Fraigniaud <>
Soumis le : lundi 12 janvier 2015 - 10:07:38
Dernière modification le : mardi 17 avril 2018 - 11:32:51

Identifiants

Collections

Citation

Hervé Baumann, Pierluigi Crescenzi, Pierre Fraigniaud. Flooding in dynamic graphs with arbitrary degree sequence. Journal of Parallel and Distributed Computing, Elsevier, 2014, 74 (5), pp.2433-2437. 〈10.1016/j.jpdc.2014.01.007〉. 〈hal-01102106〉

Partager

Métriques

Consultations de la notice

170