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

Termine:

Mi, 26.3. 16-18:30 Uhr EI 3A
Fr, 28.3. 12-13:30 Uhr HS18
Mi, 2.4. 16-17:30 Uhr EI 3A
Fr, 4.4. 12-14:30 Uhr HS18
Mo, 7.4. 16-17:30 Uhr HS1 Theresianumgasse
Mi, 9.4. 16-18:30 Uhr EI 3A
Mi, 30.4. 14-18 Uhr EI4
Mi, 7.5. 16-18:30 Uhr EI 3A
Fr, 9.5. 12-13:30 Uhr EI4

Vortragender: 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

presentation of a paper + oral exam