6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

Erik Demaine, Shay Mozes, Christian Sommer, Siamak Tazari

[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Klein's Book] [Accessibility]

Lecture 6 Video     [previous] [next]

[+] Separators in H-minor-free graphs.

As we have seen and will see in other lectures, small separators have several important applications, ranging from shortest paths to approximation schemes. They are one of the core tools that allow for faster algorithms on certain graph classes.

In this lecture, we focus on studying a result of Alon, Seymour, and Thomas, stating that every H-minor-free graph admits a small separator and such a separator can be found in polynomial (in fact, subquadratic) time. To this end, we introduce the notion of a haven and show that every graph with a haven of large order must contain a large clique as a minor. We will also briefly discuss how the concept of a knitted H-Partition introduced in the last lecture can be used to find a slightly larger separator in linear time.

Download Video: 360p, 720p

Lecture notes, page 1/12[previous page][next page][PDF]

Lecture notes, page 1/12[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.