Seminar

Speaker:	Daniel Lokshtanov (University of Bergen)
Title:	News from the width world
Date:	Παρασκευή, 26 Οκτ 2012
Ώρα:	18:15-19:30
Location:	Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών, Τμήμα Μαθηματικών, room Γ33

Abstract

Graph decomposition methods are at the core of algorithmic graph theory. Tree-width and clique-width are central notions in the theory of graph decomposition, and it has been shown that a multitude of problems enjoy fast algorithms when the input is restricted to graphs whose tree-width or clique-width is small. Most such algorithms are based on dynamic programming over the decomposition, and up until just a few years ago there were basically no improvements over the ``naive'' dynamic programming algorithms for graphs of bounded clique-width or tree-width. Over the recent years we have seen a number of results showing that many of the naive dynamic programming algorithms for graphs of bounded tree-width and clique-width are optimal, under reasonable complexity theory assumptions. These lower bound results were subsequently complemented by surprising and elegant improvements over the ``naive'' dynamic programs. In this talk i will survey the state of the art of lower- and upper-bounds on the running time of algorithms on decomposable graphs.