## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, November 06, 2018, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Stefanie Gerke (Royal Holloway University of London)

## Successive minimal paths in complete graphs with random edge weights

It is known that in a complete graph with independent exponential edge weights the distance between two fixed vertices is asymptotically almost surely (a.a.s.) log n/n. We look at the cost X_k of kth minimal path between two fixed vertices, defined as the cheapest path in G after having deleted the previous k-1 minimal paths. We show that for k = o(n^{1/3}), X_k is a.a.s. 2k/n + \log n / n. We then indicate how this can be further improved. The talk is based on joint papers with P.~Balister, B.~Mezei and G.~Sorkin.

Information for students and suggested topics for student talks