Successive shortest paths in complete graphs with random edge weights

Stefanie Gerke, Balazs Mezei, Gregory Sorkin

Research output: Contribution to journalArticlepeer-review

13 Downloads (Pure)

Abstract

Consider a complete graph Kn with edge weights drawn independently from a uniform distribution U(0,1). The weight of the shortest (minimum-weight) path P1 between two given vertices is known to be ln n/n, asymptotically. Define a second-shortest path P2 to be the shortest path edge-disjoint from P1, and consider more generally the shortest path Pk edge-disjoint from all earlier paths. We show that the cost Xk of Pk converges in probability to 2k/n + ln n/n uniformly for all k ≤ n − 1. We show analogous results when the edge weights are drawn from an exponential distribution. The same results characterise the collectively cheapest k edge-disjoint paths, i.e., a minimum-cost k-flow. We also obtain the expectation of Xk conditioned on the existence of Pk.
Original languageEnglish
Pages (from-to)1205-1247
Number of pages43
JournalRandom Structures and Algorithms
Volume57
Issue number4
Early online date13 Oct 2020
DOIs
Publication statusE-pub ahead of print - 13 Oct 2020

Cite this