Advanced Algorithms (Fall 2014)

Shay Mozes

Lecture 6 Video [previous] [next]

[+] Solving hard problems - Treewidth and Parametrized complexity

We continue the discussion of NP-Hard problems that can be solved efficiently if we assume the input is restricted in some way. We discuss interval graphs, mention other graph families, and move on to define treewidth. Finally we introduc the concepts of parameterized complexity and fixed parameter tractability (FPT). We discuss kernelization and branching - two approached for designing FPT algorithms.

Download Video: 720p

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