COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

## Successive shortest pathsAdd to your list(s) Download to your calendar using vCal - Stefanie Gerke (Royal Holloway UL)
- Thursday 02 May 2019, 14:30-15:30
- MR12.
If you have a question about this talk, please contact Andrew Thomason. The cost of the shortest path $P_1$ in a complete graph $K_n$ with random edge weights is known to converge in probability to $\ln n / n$. We define a second shortest path $P_2$ to be the cheapest path edge-disjoint from $P_1$, and consider more generally the cheapest path $P_k$ edge-disjoint from all earlier paths. We show that for $k=o(n^{1/3})$, the cost of $P_k$ converges in probability to $\ln n \, / \, n + 2k/n$, and we conjecture that a certain mild adaptation of this formula holds up to $k=n-o(n)$. We then hint how this result can be improved for fixed $k$. This talk is based on joint work with Paul Balister and Balazs Mezei and Gregory Sorkin. This talk is part of the Combinatorics Seminar series. ## This talk is included in these lists:- All CMS events
- All Talks (aka the CURE list)
- CMS Events
- Combinatorics Seminar
- DPMMS Lists
- DPMMS Pure Maths Seminar
- DPMMS info aggregator
- DPMMS lists
- MR12
- School of Physical Sciences
- bld31
Note that ex-directory lists are not shown. |
## Other listsC2AD seminar Series Information Engineering Distinguished Lecture Series Samsung AI Center Cambridge## Other talksSummer Cactus & Succulent Show Transformation and mind: Using science to fight mental illness. How We Make a Billion Antibodies: Genetics and Epigenetics The restitution of Nazi-looted art in post-fascist Austria, Italy and West Germany Creating a Commonwealth intelligence culture? Security sector reform and the politics of assistance in building the Tanzanian state, 1945-1989 Modified nucleosides, nucleotides and nucleic acids for medicinal chemistry and chemical biology |