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

Research output: Contribution to journal › Article

Forthcoming

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 language | English |
---|---|

Journal | Random Structures and Algorithms |

Publication status | Accepted/In press - 31 Aug 2020 |

ID: 38949064