Montag, 03. Dezember 2012

Kolloquiumsvortrag von Prof. Dr. Marc Pfetsch

Graphenfärbung und Symmetrien

Am Montag, dem 03. Dezember 2012 hält 

Prof. Dr. Marc Pfetsch (Universität Darmstadt)

um 16:45 Uhr im Hörsaal D2 einen Vortrag mit dem Thema

"Graphenfärbung und Symmetrien"

Zu dieser Veranstaltung sind alle Interessenten herzlich eingeladen.

Um 16:15 Uhr trifft man sich zur Begrüßung des Gastes bei Tee und Kaffee im Besprechungsraum D2.343.

 

Abstract: 

Das Ziel des Graphenfärbungsproblems ist die Zuweisung von Farben zu Knoten in einem gegebenen Graph, wobei je zwei adjazente Knoten nicht die selbe Farbe erhalten sollen und die Anzahl der verwendeten Farben minimiert werden soll. Dies ist ein wohlbekanntes Kombinatorisches Optimierungsproblem, dessen Lösung durch die Präsenz von Symmetrien in der zugehörigen Formulierung als ganzzahliges Optimierungsproblem erschwert wird. Dieser Vortrag stellt verschiedene Methoden vor, um Symmetrien zu behandeln, die in der Formulierung und im Graphen auftreten. Hierbei werden die konvexen Hüllen der zulässigen Lösungen analysiert und zugehörige lineare Ungleichungen hergeleitet. Diese Ungleichungen werden dann algorithmisch in einem exakten Branch-and-Cut Ansatz integriert. Computer-Experimente zeigen, dass Symmetrien auf diese Weise ausgenutzt werden können, um die Laufzeiten signifikant zu verbessern.


Impressum | Webmaster | Letzte Änderungen am : 23.11.2010