|
Friday, October 5, 2007 |
|
|
|
|
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. |