Albert-Ludwigs-Universität Freiburg
4pm Tuesday 9 October 2001
Room 2511, JCMB, King's Buildings
In 1999, Frick and Grohe proved that properties of graphs or other relational structures that are definable in first-order logic can be decided in linear time when the input structures are restricted to come from a locally tree-decomposable class of structures. Examples of such classes are the class of planar graphs or classes of graphs of bounded valence.
In this talk, we consider more general computational problems than decision problems. We prove that construction, listing, and counting problems definable in first-order logic can be solved in linear time on locally tree-decomposable classes of structures.
Martin Grohe
Wednesday, 17 September 2001
An error occured whilst processing this directive