Algorithmische Graphentheorie

Wintersemester 2022/23
Studiengänge: Angewandte Mathematik/M.Sc., Informatik/ M.Sc., Informatik/B.Sc. 5. Semester, Mathematik B.Sc. 5. Semester, Wirtschaftsmathematik B.Sc. 5. Semester

Inhalt

  • Erkennungs-/ Optimierungsalgorithmen für verschiedene Graphenklassen
  • strukturelle Eigenschaften von Graphen zum Entwurf effizienter Algorithmen (z.B. Baumweite von Graphen)
  • Intervallgraphen
  • chordale Graphen
  • planare Graphen

Vorlesung

Montags
Dienstag
09:15 Uhr - 10:45 Uhr
15:30 Uhr - 17:00 Uhr
ZHG/SR4
LG1A/304

Übung

Mittwochs17.30 Uhr - 19.00 UhrHG/0.18

Bitte tragen Sie sich hier in die Übungsgruppe ein.

Literatur

  • M.C. Golumbic: Algorithmic Graph Theory and Perfect Graphs. (Academic Press, 1980)
  • A. Brandstädt, V.B. Le, J.P. Spinrad: Graph Classes: A Survey. (SIAM, 1999)
  • D.B. West: Introduction to Graph Theory - 2nd ed. (Prentice Hall, 2001)
  • J.P. Spinrad: Efficient Graph Representations. (ACM, 2003)