University of Cambridge > > Combinatorics Seminar > Successive shortest paths

Successive shortest paths

Add to your list(s) Download to your calendar using vCal

  • UserStefanie Gerke (Royal Holloway UL)
  • ClockThursday 02 May 2019, 14:30-15:30
  • HouseMR12.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity