# 184.762 Graph Polynomials Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2014S

2014S, VU, 2.0h, 3.0EC

## Merkmale

• Semesterwochenstunden: 2.0
• ECTS: 3.0
• Typ: VU Vorlesung mit Übung

## Ziele der Lehrveranstaltung

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

## Inhalt der Lehrveranstaltung

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

## Weitere Informationen

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

## Vortragende Personen

• Makowsky, Johann
• Kotek, Tomer

## LVA Termine

TagZeitDatumOrtBeschreibung
Mi.16:00 - 18:3026.03.2014EI 3A Hörsaal Second Order Logic and its fragments
Fr.12:00 - 13:3028.03.2014HS 18 Czuber - MB The classical graph polynomials and their definability in SOL
Mi.16:00 - 17:3002.04.2014EI 3A Hörsaal One, two, many graph polynomials
Fr.12:00 - 14:3004.04.2014HS 18 Czuber - MB What makes a graph polynomial interesting
Mo.16:00 - 17:3007.04.2014Theresianumgasse HS 1 - MWB More graph polynomials
Mi.16:00 - 18:3009.04.2014EI 3A Hörsaal Universality properties
Mi.14:00 - 18:0030.04.2014EI 4 Reithoffer HS Complexity of graph polynomials
Mi.16:00 - 18:3007.05.2014EI 3A Hörsaal Counting graph homomorphisms
Fr.12:00 - 13:3009.05.2014EI 4 Reithoffer HS Graph polynomials in Physics and Chemistry

## Leistungsnachweis

presentation of a paper + oral exam

## LVA-Anmeldung

Nicht erforderlich

## Curricula

StudienkennzahlVerbindlichkeitSemesterAnm.Bed.Info
066 931 Computational Intelligence Gebundenes Wahlfach
066 937 Software Engineering & Internet Computing Gebundenes Wahlfach

## Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Englisch