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

[+] Contraction decomposition of bounded-genus and H-minor-free graphs: PTASs, FPT algortihms, k-cut, radial coloring, tight roots, radially shortest paths, te structures
			This lecture is about contraction decomposition: partitioning the edges of the graph into k pieces (for a specified integer k ≥ 2) such that contracting any piece reduces the graph down to bounded treewidth. We've already seen in Lecture 15 how to do this for planar graphs. In this lecture, we see how to do it in bounded-genus graphs in detail, and H-minor-free graphs at a high level. We also briefly discuss applications of contraction decomposition to PTASs and FPT algorithms. The H-minor-free contraction decomposition is a new result from STOC 2011 by Demaine, Hajiaghayi, and Kawarabayashi.

Download Video: 360p, 720p

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