mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Seminars » 2012-2013 » D. Lokshtanov, 2012-10-26 { prev, contents, next }
download seminar details: { pdf }

Seminar

Photo of Lokshtanov
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.

Comments

You must be logged in to comment.

Reporter

Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.