Lehr- und Forschungsgebiet Diskrete Optimierung

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

Gegeben einen ungerichteten Graphen $G=(V,E)$ , so fragt das Graphenfärbungsproblem (FP) nach

Wir betrachten eine Erweiterung des FP. Gesucht ist eine Färbung, d.h. eine Abbilung f, mit den zusätzlichen Eigenschaften, dass

sich die die Größen der Farbklassen um maximal eins unterscheiden, bzw.
$| | {v : f(v)=j} | - | {v : f(v)=i} | | ≤ 1 fü alle Farben i and j$ .
Mit anderen Worten: jeder Arbeiter hat maximal eine Aufgabe mehr als jeder andere Arbeiter.

Enummerierung aller möglichen Färbungen in einer Baumähnlichen Struktur. Branching und Bounding wo immer möglich.

Vergleiche das Beispiel in Figure 2. Links die baumähnliche Nummerierung der Färbungen, rechts die entsprechende Graphenfärbung.

letzte Änderung: 10.09.2016 - 16:02