Seminar Algorithmen in der Graphentheorie

Inhalt

Graphen spielen eine entscheidene Rolle in der Informatik. Um die Effizienz bekannter Algorithmen zu verbessern, werden oft planare Graphen betrachtet; sie sind nach wie vor Gegenstand aktueller Forschung. In diesem Seminar werden u.a. Algorithmen behandelt, die sich ”unterhalb” der Komplexitätsklasse P befinden. Mögliche Themen sind z.B. Fluss- und Matchingalgorihmen, Algorithmen zur Einbettung von Graphen in einer planaren Ebene, Erreichbarkeitsprobleme,... .

Zeitplan

Kalenderwoche Verfügbare Wochen Arbeitsschritt
15 1 Vergabe der Themen und des Materials
15-20 5 Literaturrecherche und Erstellung einer detaillierten Gliederung der Arbeit
Dienstag, 17. Mai, KW20 Abgabe der Gliederung
Freitag, 20. Mai, 10 Uhr, KW20 Vortrag zum Erstellen einer wissenschaflichen Ausarbeitung, Raum o27/531
20-21 2 Besprechung der Gliederung, Termin wird individuell per Mail ausgemacht
21-24 4 Erstellung der Ausarbeitung
Freitag, 17. Juni, KW24 Abgabe der Ausarbeitung
25-26 2 Ausarbeitungen werden korrigiert. Besprechung der Ausarbeitung.
27 1 Korrekturen einbringen
Sonntag, 10. Juli, KW27 Abgabe der korrigierten Ausarbeitung
(24-) 28 (4) 1 Präsentation vorbereiten
Sonntag, 17. Juli, KW28 Abgabe einer Vorabversion der Präsentation
Mittwoch, 20. Juli, KW29 Vorstellung der Präsentation

Betreuer

Simon Straub, Prof. Dr. Uwe Schöning

Termine