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

In: Random Structures and Algorithms, 31.08.2020.

Research output: Contribution to journalArticle

Forthcoming

Documents

  • Accepted Manuscript

    Accepted author manuscript, 669 KB, PDF document

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
Publication statusAccepted/In press - 31 Aug 2020

ID: 38949064