University of Cambridge > > Computer Laboratory Automated Reasoning Group Lunches > Evaluating Formulas on Graphs

Evaluating Formulas on Graphs

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Thomas Tuerk.

We consider the computational complexity of the following problem: given a first-order formula f in the language of graphs (i.e. with one binary relation) and a finite graph G, determine whether f is satisfied in G. The complexity is generally exponential in the size of f, though polynomial in the size of G. The problem is quite general and encompasses many known hard decision problems on graphs. I well explain how the problem can be made more tractable on restricted classes of graphs, which will lead us to a brief exploration of graph structure theory.

This talk is part of the Computer Laboratory Automated Reasoning Group Lunches series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity