Computability in Europe 2006
Logical Approaches to Computational Barriers

Invited Plenary Talk:
Uniform algebraic reducibilities between parameterized numeric graph invariants

Speaker: Johann Makowsky


We report about our ongoing study of inter-reducibilities of parameterized numeric graph invariants and graph polynomials. The purpose of this work is to systematize recent emerging work on graph polynomials and various partition functions with respect to their combinatorial expressiveness and computational complexity.

websites: Arnold Beckmann 2008-03-25