|
|
 | |
abstract 07-05-16.php
Die Rotationsdimension von Graphen
Markus Wappler Mi. 16.05.2005
Abstract:
Wir studieren das Problem der Maximierung des zweitkleinsten Eigenwertes der
Laplacematrix eines Graphen über nichtnegative Kantengewichte mit einem
Gesamtgewicht von höchstens Eins. Mit Techniken der semidefiniten Optimierung
lässt sich zeigen, dass das Duale hierzu äquivalent zu einem
Einbettungsproblem von n Knoten in den R^n ist. Optima der primalen Aufgabe
korrespondieren mit Gleichgewichtssituationen des Einbettungsproblems. Wir
charakterisieren Gleichgewichtssituationen und Graphen, für die Einbettungen
niedriger Dimension existieren.
|
