zum Inhalt springen

Musterveranstaltung

Anhand einzelner Textbuchkapitel und Originalarbeiten sollen Inhalte der Vorlesung im SS09 vertieft und weiterführende Fragestellungen behandelt werden. Dabei sollen die Algorithmik und damit verbundene Komplexitätsfragen eine wesentliche Rolle spielen. Mögliche Themen sind:

  • Beziehung zwischen numerischer linearer Algebra und spektraler Graphentheorie (insbesondere unter algorithmischem Gesichtspunkt)
  • Algorithmen zur Erkennung von Symmetrien in Graphen. Insbesondere Behandlung des Graphisomorphieproblems.
  • Färbungsalgorithmen. Insbesondere für planare Graphen.
  • Graphpolynomauswertung (insb. Rangpolynom); zugehörige Algorithmen.

Vorbesprechung: Freitag, 14.8.2009, 12.00-13.00 Uhr

Literatur:

  • Biggs, N.: Algebraic Graph Theory. 3. Auflage, Cambridge University Press, 1994.
  • Godsil, C.; Royle, G.: Algebraic Graph Theory. In: Graduate Texts Mathematics, Springer-Verlag, 2001.
  • Bollobas, B.: Modern Graph Theory. In: Graduate Texts in Mathematics Springer-Verlag, 1998.