Personal tools
You are here: Home Events Abstract Archives 2006-2007 Algorithmic Meta-theorems

Algorithmic Meta-theorems

Martin Grohe Humboldt-Universit├Ąt zu Berlin 4pm Tuesday 28th August 2007 Room 2511, JCMB, King's Buildings

Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic can be decided in linear time on graphs of bounded tree width. More recent examples of such meta theorems state that all first-order definable properties of planar graphs can be decided in linear time and that all first-order definable optimisation problems on classes of graphs with excluded minors can be approximated in polynomial time to any given approximation ratio.

This talk will be a survey of algorithmic meta theorems and the main techniques used to prove such theorems.

Document Actions