What is... the Disjoint Paths Problem?

This page hosts information on Miriam Schlöter's talk "What is ... the Disjoint Paths Problem?" at the "What is ...?" seminar. This talk will help you better understand the talk by Lex Schrijver.

Where & When

• Friday, February 12, 2016, 1pm at the BMS seminar room MA212 at TU

Abstract

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.

Comments