Desktop-Bild

Projekt: Branch- and Bound Algorithmen für das equitable Graphenfärbungsproblem

Förderung: DFG Exellence Initiative
Lehrstuhl II für Mathematik, Lehr- und Forschungsgebiet Diskrete Optimierung
RWTH Aachen University
Übersicht / Das equitable Färbungsproblem / Code und Data /


Projektbeschreibung

Dem Projekt liegt das equitable Färbungsproblem (EFP) zugrunde. Hierbei handelt es sich um eine Variante des Graphenfärbungsproblems, bei dem die zu bestimmenden Farbklassen eine ähnliche Kardinaliät aufweisen sollen. Ein bekanntes Anwendungsbeispiel kommt aus dem Bereich des Scheduling, dort sollen (in Konflikt stehende) Arbeitsaufträge (Ecken des Graphen) möglichst ausgeglichen auf mehrere Maschinen (Farben) verteilt werden.
equitableColoring
Fig.1 - Eine equitable Färbung

Aufbauend auf das Undergraduate Funds Projekt Implementierung eines neuen Branch and Bound Verfahrens für das equitable Färbungsproblem (IBBVeF) sollen die dort erzielten Resultate vertieft und erweitert werden. In diesem Projekt implementierte der Student Sven Förster für das EFP Problem einen Branch-and-Bound Algorithmus welcher vielversprechende Resultate lieferte. Im Rahmen dieses Projektes wurden interessante Perspektiven für weitere Forschung aufgezeigt. Daher bietet es sich an die wissenschaftliche Arbeit in diesem Themenkomplex auszubauen. Hierzu soll die wissenschaftliche Theorie erweitert und erzielte Resultate in die bisher erstellte Software integriert werden.

Mitarbeiter

Projektleiter: Prof. Arie M.C.A. Koster
Dr. Robert B. Scheidweiler
Martin Tieves
Studentische Hilfskräfte: Duc Thanh Tran und Sven Förster (ehemalig)


Publikationen

Einführung in die Thematik: A DSATUR-based algorithm for the Equitable Coloring Problem, Méndez-Díaz, Nasini und Severín (link).
Preprint (Arxiv): A flow based pruning scheme for enumerative equitable coloring algorithms, Koster, Scheidweiler und Tieves (link).


Konferenzbeiträge

A flow based pruining scheme for enumerative equitable coloring algorithms, Martin Tieves, INFORMS Optimization Society Conference 2016, Princeton, NY, US (link).

Pruining Schemes for DSATUR algorithms for equitable graph coloring, Robert Scheidweiler, Oberseminar, Zuse Institute, Berlin, Germany.

Generating Pruning Rules For Enumerative Equitable Coloring Algorithms, International Symposium on Combinatorial Optimisation 2016, University of Kent, Canterbury, UK.
letzte Änderung: 13.02.2017 - 16:18