Friday, October 5, 2007 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
The k-Linkage Problem for Graphs
| Speaker: | Jim Geelen |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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.