Journées GALET

Treewidth and exact algorithms

F. Fomin
University of Bergen

Abstract: Tree-width is one of the most basic parameters in graph algorithms. There is a well established theory on the design of polynomial (or even linear) time algorithms for many intractable problems when the input is restricted to graphs of bounded tree-width. In this talk I give an overview of treewidth applications in the area of exact algorithms. The talk is based on joint work with Hans Bodlaender, Frederic Dorn, Serge Gaspers, Kjartan Hoie, Elko Penninkx, Saket Saurabh, and Dimitrios Thilikos.


Frederic Havet
Last modified: Wed Jun 7 09:42:56 MEST 2006