135. Informatik-Kolloquium
Öffentliche Verteidigung im Rahmen des Promotionsverfahrens
Herr Dipl.-Inf. André Lanka
TU Chemnitz
Fakultät für Informatik
Professur Theoretische Informatik
"Spektrale Algorithmen - Mit Eigenwerten schwierige Probleme lösen"
Freitag, 25.04.2008
10:00 Uhr, 1/219
Alle interessierten Personen sind herzlich eingeladen!
Inhalt:
Inhalt: Bei der Partitionierung von Graphen versucht man, Strukturen in Graphen zu finden (etwa 3-Färbungen oder kleine Bisektionen). Derartige Probleme lassen sich im worst-case nur in Exponentialzeit bewältigen. Die worst-case-Graphen treten allerdings vergleichsweise selten auf, sodass es für den "typical-case" auch Algorithmen mit polynomieller Laufzeit geben kann. Um Aussagen über diesen typical-case zu erhalten, analysiert man den Algorithmus auf zufälligen Graphen.
Wir stellen einen Algorithmus vor, der auf einem sehr allgemeinen Modell für
Zufallsgraphen bewiesenermaßen sehr gute Dienste leistet. Die zu findende Struktur
extrahiert der Algorithmus aus den Eigenwerten und Eigenvektoren einer speziellen Matrix,
die wiederum aus dem eingegebenen Graphen konstruiert wird.
Die Gesamtlaufzeit des Verfahrens ist n^3, also polynomiell in der Knotenzahl n.
