- Series
- Graph Theory Seminar
- Time
- Friday, June 11, 2010 - 4:20pm for 1 hour (actually 50 minutes)
- Location
- Skiles 254
- Speaker
- Paul Wollan – The Sapienza University of Rome
- Organizer
- Robin Thomas
The theory of graph minors developed by Robertson and Seymour is
perhaps one of the deepest developments in graph theory. The theory is
developed in a sequence of 23 papers, appearing from the 80's through
today. The major algorithmic application of the work is a polynomial
time algorithm for the k disjoint paths problem when k is fixed. The
algorithm is relatively simple to state - however the proof uses the
full power of the Robertson Seymour theory, and consequently runs
approximately 400-500 pages. We will discuss a new proof of
correctness that dramatically simplifies this result, eliminating many
of the technicalities of the original proof.
This is joint work with Ken-ichi Kawarabayashi.