Department of Mathematics

Indian Institute Of Technology Madras , Chennai

Courcelle's theorem

Speaker : Prof Kamal Lodaya, IMSc, Chennai.


Abstract :

Consider a property of finite graphs written in predicate logic, even allowing quantifiers over sets of vertices and edges. Courcelle (1990) gives an algorithm to check such a property which is linear in the size of the graph, parameterized by a computable function in the treewidth of the graph and the size of the formula describing the property. (Sometimes this is described as a fixed parameter linear time algorithm.) This talk gives a gentle introduction to the logic and the algorithm.

Key Speaker Prof Kamal Lodaya, IMSc, Chennai.
Place Madhava Hall
Start Time 3:00 PM
Finish Time 4:00 PM
External Link None