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]

Lecture 16 Video     [previous] [next]

[+] PTAS for planar subset-connectivity problems I: construction of a mortar graph-brick decomposition and spanner for subset TSP and Steiner tree

In this lecture we study the breakthrough result of Borradaile, Klein, and Mathieu regarding a PTAS for Steiner tree in planar graphs. Steiner tree is a subset-type problem, where we mainly care about a given subset of terminals in the graph. In particular, the weight of a Steiner tree can be arbitrarily smaller than the minimum spanning tree of the graph. This makes it very different from all problems we have studied so far.

In the previous lecture we got acquainted with Klein's framework for designing PTASes in planar graphs and applied it to the TSP problem. In this lecture, we review this framework and see how to apply it to the Steiner tree problem. We will see that the most difficult step is to obtain a spanner. We study the so called mortar graph-brick decomposition and how it gives rise to a spanner. This decomposition has been applied to further problems as well and has been generalized to bounded-genus graphs.

In Lecture 16 we will describe the algorithm and its correctness based on a structure theorem. The structure theorem itself is presented in Lecture 17.

Download Video: 360p, 720p

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

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