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: |
FOS: Computer and information sciences
Uniform distribution (continuous) Exponential distribution Discrete Mathematics (cs.DM) General Mathematics 0102 computer and information sciences Edge (geometry) 01 natural sciences 68Q87 05C80 60C05 05C22 90B15 Combinatorics FOS: Mathematics Mathematics - Combinatorics QA Mathematics Mathematics Applied Mathematics Probability (math.PR) Complete graph Computer Graphics and Computer-Aided Design 010201 computation theory & mathematics Shortest path problem Path (graph theory) Combinatorics (math.CO) Minimum-cost flow problem Dijkstra's algorithm Mathematics - Probability Software Computer Science - Discrete Mathematics |
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 |
Externí odkaz: |
Pro tento záznam nejsou dostupné žádné jednotky.