Seminar über "Algorithmische Aspekte der Algebraischen Graphentheorie"

Stefan Porschen

Anhand einzelner Textbuchkapitel und Originalarbeiten sollen Inhalte der Vorlesung im SS03 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.

Evtl. Fragen können Sie per E-Mail an Stefan Porschen richten.

Literatur

• N. Biggs, Algebraic Graph Theory, 3. Auflage, Cambridge University Press, 1994.
• C. Godsil, G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, 2001.
• B. Bollobas, Modern Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, 1998.
• D. Cvetkovic, P. Rowlinson, S. Simic, Eigenspaces of graphs, Cambridge Univ. Press, 1997
• M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, 1991
• T. R. Jensen, B. Toft, Graph coloring problems, Wiley, 1995
• J. Köbler, U. Schöning, J. Toran, The graph isomorphism problem: its structural complexity, Birkhäuser, 1993

Weitere spezielle Literatur insbesondere Originalarbeiten wurden im Rahmen der Vorbesprechung angegeben.