$\vec{w}h\alpha\mathfrak{t}\;\; i\mathbb{S}\ldots$

the disjoint paths problem?

Miriam Schröder (TU Berlin)
2016/02/12, 13:00
Before the BMS Friday Colloquium by Prof. Lex Schrijver.
Urania Berlin, at the BMS Loft (3rd floor)
About what?

Imagine you are an electrical engineer and responsible for the power supply of a town. By building a large network of transmission towers you connected the town to the nearest power plant. Now your boss asks you to prove to him that the power supply of the town is still ensured if k transmission towers fail. How can you convince your boss that the network you built is failsafe? Of course, you can simply switch out every possible k-subset of transmission towers and check whether the city is still on power supply after that. Unfortunately, you built a large network, so this approach would take a long time. A good solution in this situaion would be to use Menger's theorem which provides us with a fast to check certificate that ensures that the network is failsafe. In this talk I will introduce Menger's Theorem and the related disjoint paths problem in different variants.