Algorithms for Planar Graphs (Fall 2015)

Shay Mozes

Lecture 10 Video [previous] [next]

[+] Branchwidth and Baker's approximation technique

The lecture starts with a breif discussion of problems from the second problem set. We then finish our short discussion of exact distance oracles by showing an oracle with nearly linear space and roughly squre-root query time. We present Baker's approximation scheme by showing its instantiation on the vertex cover problem.

Download Video: 720p

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