mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Seminars » 2012-2013 » D. Lokshtanov, 2012-10-26 { prev, contents, next } Anonymously browsing from 54.81.44.140 at 15:18:22, 24-09-2017. login
download seminar details: { pdf }

Seminar

Photo of Lokshtanov
Speaker: Daniel Lokshtanov (University of Bergen)
Title: News from the width world
Date: Friday, 26 Oct 2012
Time: 18:15-19:30
Location: Univeristy of Athens, Department of Mathematics, University of Athens, 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

Page updates

No recent updates.

Feeds RSS and Atom feeds

posts
all posts RSS
news RSS
announcements RSS
website news RSS
events
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.