- AutorIn
- André Lanka
- Titel
- Spektrale Algorithmen - Mit Eigenwerten schwierige Probleme lösen
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:ch1-200800468
- Datum der Einreichung
- 16.01.2008
- Datum der Verteidigung
- 25.04.2008
- Abstract (DE)
- 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.
- Klassifikation (DDC)
- 004
- Normschlagwörter (GND)
- Aussagenlogik
- Bisektionsproblem
- Erfüllbarkeitsproblem
- Graphen
- Graphfärbung
- Partitionierung
- Stochastische Matrix
- GutachterIn
- Prof. Dr. Andreas Goerdt
- PD Amin Coja-Oghlan
- Prof. Dr. Hanno Lefmann
- BetreuerIn
- Prof. Dr. Andreas Goerdt
- Den akademischen Grad verleihende / prüfende Institution
- Technische Universität Chemnitz, Chemnitz
- URN Qucosa
- urn:nbn:de:bsz:ch1-200800468
- Veröffentlichungsdatum Qucosa
- 25.04.2008
- Dokumenttyp
- Dissertation
- Sprache des Dokumentes
- Deutsch