A common generalization of counting problems are graph polynomials. The most prominent of these are the matching polynomials, the colouring polynomials and the Tutte polynomial. For general graphs these are often hard to compute (#P hard). There are also various multivariate generalizations of these polynomials.
2) Reducibilities between graph polynomials
3) Towards an algebraic complexity theory
4) Recursively constructed graphs
5) Tree-width, clique-width and beyond
See also http://www.cs.technion.ac.il/~janos/COURSES/238900
A common generalization of counting problems are graph polynomials. The most prominent of these are the matching polynomials, the colouring polynomials and the Tutte polynomial. For general graphs these are often hard to compute (#P hard). There are also various multivariate generalizations of these polynomials.
2) Reducibilities between graph polynomials
3) Towards an algebraic complexity theory
4) Recursively constructed graphs
5) Tree-width, clique-width and beyond
See also http://www.cs.technion.ac.il/~janos/COURSES/238900
Dates of the lecture:
Wed, 26.3., 4 pm - 6:30 pm in EI 3A
Fri, 28.3., 12 pm - 1:30 pm in HS18
Wed, 2.4., 4 pm - 5:30 pm in EI 3A
Fri, 4.4., 12 pm - 2:30 pm in HS18
Mon, 7.4., 4 pm - 5:30 pm in HS1 Theresianumgasse
Wed, 9.4., 4 pm - 6:30 pm in EI 3A
Wed, 30.4., 2 pm - 6 pm in EI4
Wed, 7.5., 4 pm - 6:30 pm in EI 3A
Fri, 9.5. 12 pm - 1:30 pm in EI4
Lecturer: Johann Makowsky janos@cs.technion.ac.il
ECTS-BREAKDOWN:
- 30 hours of lectures
- 25 hours of reading lecture material outside of class.
- 20 hours for preparing and presenting a paper from the literature
