Flooding And Diameter In General Weighted Random Graphs

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, and the flooding time, which represents the time (weighted length) needed to reach all the vertices in the graph starting from a uniformly chosen vertex. Our result consists in describing the asymptotic behavior of the diameter and the flooding time, as the number of verticesntends to infinity, in the case where the weight distributionGhas an exponential tail behavior, and proving that this category of distributions is the largest possible for which the asymptotic behavior holds.


Published in:
Journal Of Applied Probability, 57, 3, 956-980
Year:
Sep 01 2020
Publisher:
Cambridge, CAMBRIDGE UNIV PRESS
ISSN:
0021-9002
1475-6072
Keywords:




 Record created 2020-09-17, last modified 2020-10-29


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)