The k-Linkage Problem for Graphs
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1