Journal article
Successive shortest paths in complete graphs with random edge weights
- 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 a...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Bibliographic Details
- Publisher:
- Wiley Publisher's website
- Journal:
- Random Structures and Algorithms Journal website
- Volume:
- 57
- Issue:
- 4
- Pages:
- 1205-1247
- Publication date:
- 2020-10-13
- Acceptance date:
- 2020-08-20
- DOI:
- EISSN:
-
1098-2418
- ISSN:
-
1042-9832
Item Description
- Language:
- English
- Keywords:
- Pubs id:
-
1135113
- Local pid:
- pubs:1135113
- Deposit date:
- 2020-09-27
Terms of use
- Copyright holder:
- Gerke et al.
- Copyright date:
- 2020
- Rights statement:
- ©2020 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.
- Notes:
- This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record