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 10 Video [previous] [next]

[+] Approximation schemes in minor-free graphs II: Bidimensionality: Subexponential FPT algorithms and EPTAS

In this lecture we will explore bidimensionality - a powerful theory that encompasses and unifies a very large fraction of what we know algorithmically about planar and H-minor-free graphs as far as PTASes and parameterized algorithms go. The main idea of how to establish parameter-treewidth bounds using grids is very simple and easy to grasp and immediately leads to subexponential parameterized algorithms for a large number of problems. After that, we study an abstract framework of how to derive EPTASes for many of our favorite problems using bidimensionality as the backbone.

Download Video: 360p, 720p

Lecture notes, page 1/11 • [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.