Proseminar Graphalgorithmen

In diesem Proseminar betrachten wir Probleme auf Graphen und deren algorithmische Komplexität. Grundlage bildet das Buch "Algorithmic Graph Theory" von Alan Gibbons, Cambridge University Press. Die Themen sind:

• Spannbäume und Verzweigungen
• Schnittmengen und Zusammenhang
• Ebene Graphen
• Netzwerke und Flüsse
• Paarungen
• Eulersche und Hamiltonsche Touren
• Färbungen von Graphen
• Graphprobleme und NP-Vollständigkeit