Eintrag in der Universitätsbibliographie der TU Chemnitz
Volltext zugänglich unter
URN: urn:nbn:de:bsz:ch1-200800468
Lanka, André
Coja-Oghlan, Amin (PD) ; Goerdt, Andreas (Prof. Dr.) ; Lefmann, Hanno (Prof. Dr.) (Gutachter)
Spektrale Algorithmen - Mit Eigenwerten schwierige Probleme lösen
Kurzfassung in deutsch
Bei der Partitionierung von Graphen versucht man, Strukturen in Graphen zu finden (etwa 3-Färbungen oder kleine Bisektionen). Mithilfe von Eigenwerten und Eigenvektoren können solche Probleme oftmals effizient gelöst werden. Wir stellen einen Algorithmus vor, der auf einem sehr allgemeinen Modell für zufällige Graphen bewiesenermaßen sehr gute Dienste leistet.Weiterhin untersuchen wir zufällige 3Sat-Formeln. Hier wollen wir mit Eigenwerten obere Schranken an die Anzahl der erfüllbaren Klauseln finden. Die gefundenen Schranken sind (in den meisten Fällen) nahezu optimal.
| Universität: | TU Chemnitz | |
| Institut: | Professur Theoretische Informatik | |
| Fakultät: | Fakultät für Informatik | |
| Dokumentart: | Dissertation | |
| Betreuer: | Goerdt, Andreas (Prof. Dr.) | |
| URL/URN: | http://archiv.tu-chemnitz.de/pub/2008/0046 | |
| SWD-Schlagwörter: | Aussagenlogik , Bisektionsproblem , Erfüllbarkeitsproblem , Graphen , Graphfärbung , Partitionierung , Stochastische Matrix | |
| DDC-Sachgruppe: | Datenverarbeitung; Informatik | |
| Tag der mündlichen Prüfung | 25.04.2008 |
