Successive shortest paths in complete graphs with random edge weights
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Wiley
2020
|