Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Flooding And Diameter In General Weighted Random Graphs
 
research article

Flooding And Diameter In General Weighted Random Graphs

Mountford, Thomas  
•
Saliba, Jacques  
September 1, 2020
Journal Of Applied Probability

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.

  • Details
  • Metrics
Type
research article
DOI
10.1017/jpr.2020.45
Web of Science ID

WOS:000565709200014

Author(s)
Mountford, Thomas  
Saliba, Jacques  
Date Issued

2020-09-01

Publisher

CAMBRIDGE UNIV PRESS

Published in
Journal Of Applied Probability
Volume

57

Issue

3

Start page

956

End page

980

Subjects

Statistics & Probability

•

Mathematics

•

first passage percolation

•

configuration model

•

diameter

•

flooding time

•

continuous branching process

•

1st passage percolation

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
PRST  
Available on Infoscience
September 17, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/171708
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés