Lecture notes, page 1/12 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/12 • [previous page] • [next page] • [PDF]
[+] 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. |
|
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.