Friday, October 5, 2007 



The kLinkage Problem for Graphs 

The klinkage 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 klinkage problem can be solved in polynomial time. In this talk I will give an overview of their algorithm. 