Successive shortest paths in complete graphs with random edge weights

Gerke, Stefanie, Mezei, Balazs F. and Sorkin, Gregory (2020) Successive shortest paths in complete graphs with random edge weights. Random Structures and Algorithms, 57 (4). 1205 - 1247. ISSN 1042-9832

Text (Successive shortest paths in complete graphs with random edge weights) - Published Version Available under License Creative Commons Attribution. Download (967kB)

• Author

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 characterize the collectively cheapest k edge-disjoint paths, that is, a minimum-cost k-flow. We also obtain the expectation of Xk conditioned on the existence of Pk.

Item Type:	Article
Official URL:	https://onlinelibrary.wiley.com/journal/10982418
Additional Information:	© 2020 The Authors
Divisions:	Mathematics
Subjects:	Q Science > QA Mathematics
Date Deposited:	04 Sep 2020 10:06
Last Modified:	20 Sep 2025 01:55
URI:	http://eprintstest.lse.ac.uk/id/eprint/106487

Actions (login required)

View Item