Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Research Seminar

Christian Hoffmann: Solving Hard Graph Problems Using Tree Decompositions

June 10, 2008, 10:15 a.m.
E 1 3, Room 415

Many graph problems which are NP-hard in general can be solved in polynomial time if the input is restricted to graphs of bounded tree width. We will introduce the notion of tree decomposition and tree width and give examples of algorithms which use tree decompositions to solve hard problems on graphs of bounded tree width in polynomial time.