The flooding time in random graphs
type: Item
instance of: scholarly article
title: The flooding time in random graphs
zbMATH Open document ID: 1035.60094
DOI: 10.1023/A:1022175620150
author: Remco van der Hofstad
author: Gerard Hooghiemstra
author: Piet Van Mieghem
published in: Extremes
publication date: 2004-03-16T00:00:00Z
review text: Asymptotics of the flooding time \(T_n(p)\) (i.e. a time of first-passage percolation) in a random graph \(G_p(N)\) is considered. The graph \(G_p(N)\) has \(N\) nodes and each pair of nodes is connected by a link with probability \(p=p_N\) independently from others. The links are weighted by exponentially distributed random variables with mean 1. (The weight of a link is the time needed to pass through the link.) It is shown that if \(Np_N/(\log N)^3\to\infty\) as \(N\to\infty\), then \[ \lim_{N\to\infty}\Pr\{Np_N T_N(p_N)-2\log N< z\}=\Lambda^{(2*)}(z), \] where \(\Lambda^{(2*)}\) denotes the two-fold convolution of the Gumbel distribution function \(\Lambda\).
Mathematics Subject Classification ID: 60K35
Mathematics Subject Classification ID: 60J25
zbMATH DE Number: 2059062
zbMATH Keywords: first-passage percolation
zbMATH Keywords: limit distribution
zbMATH Keywords: asymptotic behaviour
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2059062