Successive shortest paths in complete graphs with random edge weights. / Gerke, Stefanie; Mezei, Balazs; Sorkin, Gregory.

In: Random Structures and Algorithms, 13.10.2020.

Research output: Contribution to journalArticle

E-pub ahead of print

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
JournalRandom Structures and Algorithms
Early online date13 Oct 2020
DOIs
Publication statusE-pub ahead of print - 13 Oct 2020
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 38949064