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.