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 3AFr, 28.3. 12-13:30 Uhr HS18Mi, 2.4. 16-17:30 Uhr EI 3AFr, 4.4. 12-14:30 Uhr HS18Mo, 7.4. 16-17:30 Uhr HS1 TheresianumgasseMi, 9.4. 16-18:30 Uhr EI 3AMi, 30.4. 14-18 Uhr EI4Mi, 7.5. 16-18:30 Uhr EI 3AFr, 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
Nicht erforderlich