ZBVI.01k Vorlesung Algorithmische Graphentheorie
Brandenburgische Technische Universität Cottbus


Lehrstuhl für
Mathematische Grundlagen der Informatik

W. Hochstättler, B. Jackson: Large Circuits in Binary Matroids of Large Cogirth (Part I)

Algorithmische Graphentheorie

Vorlesungszeiten

Dienstags 15.30 Uhr - 17:00 Uhr ZBVI.01
Donnerstags 11.30 Uhr - 13.00 Uhr LG1A/110a
Sondertermin:
Donnerstags, 16.06.2005 9.15 Uhr - 10.45 Uhr ZBVI.01

Eine Vielzahl interessanter Optimierungsprobleme auf Graphen ist algorithmisch sehr schwer zu lösen. Als Beispiel sei das Graphfärbungsproblem oder das Hamiltonkreisproblem genannt. Betrachtet man praktische Anwendungen in denen solche Optimierungsprobleme eine Rolle spielen, so sind für die entsprechenden Graphen oft sehr spezielle Struktureigenschaften bekannt. Setzt man diese Eigenschaften voraus, lassen sich die betrachteten Optimierungsprobleme oft mit sehr schnellen Algorithmen exakt lösen.

Das Gebiet der Algorithmischen und Strukturellen Graphentheorie beschäftigt sich mit der Untersuchung solcher Struktureigenschaften und dem Entwurf effizienter Algorithmen für spezielle Graphenklassen. In dieser Vorlesung werden wir uns mit einer Reihe von Graphenklassen genauer beschäftigen, so z.B. mit Intervallgraphen, chordalen Graphen, planaren Graphen und Vergleichbarkeitsgraphen. Für jede der Graphenklassen werden wir charakteristische Struktureigenschaften bestimmen, Erkennungsalgorithmen entwickeln und schließlich verschiedene effiziente Algorithmen für Optimierungsprobleme entwerfen.

Die Vorlesung wird als integrierte Veranstaltung angeboten, d.h. es werden regelmäßig Übungsblätter ausgegeben, die dann von den Teilnehmern bearbeitet und in integrierten Übungen besprochen werden. Die regelmäßige Teilnahme und Mitarbeit bei den Übungen ist Voraussetzung für die Teilnahmebestätigung.

Literatur

  • M.C. Golumbic: "Algorithmic Graph Theory and Perfect Graphs", Elsevier, 2004.
  • 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.


nickel@math.tu-cottbus.de