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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:ch1-200800468 |
| Date | 25 April 2008 |
| Creators | Lanka, André |
| Contributors | TU Chemnitz, Fakultät für Informatik, Prof. Dr. Andreas Goerdt, PD Amin Coja-Oghlan, Prof. Dr. Andreas Goerdt, Prof. Dr. Hanno Lefmann |
| Publisher | Universitätsbibliothek Chemnitz |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | deu |
| Detected Language | German |
| Type | doc-type:doctoralThesis |
| Format | application/pdf, text/plain, application/zip |
Page generated in 0.0015 seconds