Navigation

Springe zum Hauptinhalt
Fakultät für Informatik
Informatik-Kolloquien

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.

Presseartikel