Alexander Schrijver: The partially disjoint paths problem

Abstract: The partially disjoint paths problem asks for paths P1,…,Pk between given pairs of terminals, while certain pairs of paths Pi,Pj are required to be disjoint. With the help of combinatorial group theory, we show that, for fixed k, this problem can be solved in polynomial time for planar directed graphs. We also discuss related problems. No specific foreknowledge is required.

Recording during the “IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2017)” the September 12, 2017 at the Centre International de Rencontres Mathématiques (Marseille, France)

Filmmaker: Guillaume Hennenfent

Find this video and other talks given by worldwide mathematicians on CIRM’s Audiovisual Mathematics Library: And discover all its functionalities:
– Chapter markers and keywords to watch the parts of your choice in the video
– Videos enriched with abstracts, bibliographies, Mathematics Subject Classification
– Multi-criteria search by author, title, tags, mathematical area


About the author