Successive shortest paths in complete graphs with random edge weights

Autor: Balázs F. Mezei, Stefanie Gerke, Gregory B. Sorkin
Rok vydání: 2020
Předmět:
Zdroj: Random Structures & Algorithms. 57:1205-1247
ISSN: 1098-2418
1042-9832
DOI: 10.1002/rsa.20962
Popis: Consider a complete graph $K_n$ with edge weights drawn independently from a uniform distribution $U(0,1)$. The weight of the shortest (minimum-weight) path $P_1$ between two given vertices is known to be $\ln n / n$, asymptotically. Define a second-shortest path $P_2$ to be the shortest path edge-disjoint from $P_1$, and consider more generally the shortest path $P_k$ edge-disjoint from all earlier paths. We show that the cost $X_k$ of $P_k$ converges in probability to $2k/n+\ln n/n$ uniformly for all $k \leq 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 $X_k$ conditioned on the existence of $P_k$.
Databáze: OpenAIRE
Pro tento záznam nejsou dostupné žádné jednotky.