Hamed Amini
Shortest-weight paths in random graphs
Abstract:
Consider a random regular graph with degree d and of size n. Assign to each edge an i.i.d. exponential random variable with mean one. In the first part, we establish a precise asymptotic expression for the maximum number of edges on the shortest-weight paths between a fixed vertex
and all the other vertices, as well as between any pair of vertices. This is a joint work with Yuval Peres. We then analyze the impact of the edge weights on distances in sparse random graphs. Our main result consists of a precise asymptotic expression for the weighted diameter of sparse random graphs when the edge weights are i.i.d. exponential random variables. This is based on a joint work with Marc Lelarge.