Friday, October 5, 2007
3:30 pm, MC 5158

Tutte Seminar Series
Combinatorics & Optimization
Fall 2007

Jim Geelen
University of Waterloo

The k-Linkage Problem for Graphs

The k-linkage problem is the problem of finding internally disjoint paths connecting k prescribed pairs of vertices in a given graph. As part of their celebrated graph minors project, Robertson and Seymour showed that the k-linkage problem can be solved in polynomial time. In this talk I will give an overview of their algorithm.