[Zurück]


Diplom- und Master-Arbeiten (eigene und betreute):

C. Volko:
"Selective Graph Coloring Problem";
Betreuer/in(nen): G. Raidl, B. Hu; Institut für Computergraphik and Algorithmen, 2013; Abschlussprüfung: 04/2013.



Kurzfassung deutsch:
Beim Selective Graph Coloring Problem (SGCP) geht es darum, einen Teilgraphen mit spezieller
Struktur zu finden, dessen chromatische Zahl so niedrig wie möglich ist. Der Ursprungsgraph ist in
mehrere Cluster unterteilt, und von jedem Cluster muss der Teilgraph genau einen Knoten enthalten.
Dieses Problem ist NP-schwer und wird daher meistens mit Heuristiken gelöst.
Ich habe mehrere Varianten eines Algorithmus implementiert, der Variable Neighborhood Search
(VNS) benutzt, um den Lösungsraum zu durchsuchen, und dann die gefundene Lösung mit
heuristischen oder exakten Methoden evaluiert. Jede Variante kann mit oder ohne ein Lösungsarchiv
verwendet werden. Ein Lösungsarchiv ist eine Datenstruktur, in der bereits gefundene Lösungen
gespeichert werden, so dass Duplikate nicht neu evaluiert werden müssen, sondern effizient zu
neuen Lösungen konvertiert werden können. Um eine obere Schranke zu errechnen, wurde eine
Variante von Greedy Coloring verwendet. Eine weitere Variante des Algorithmus zählt auch die
Anzahl der Konflikte, die entstünden, würde eine Farbe weniger verwendet werden. Schließlich
wurden zwei Methoden umgesetzt, um eine untere Schranke zu berechnen: maximale Clique und
lineare Programmierung mit Spaltengenerierung.
Das Programm wurde mit verschiedenen Instanzen aus der Literatur getestet. Mein Algorithmus
beendete die Berechnungen oft schon nach sehr kurzer Laufzeit, führte aber im Allgemeinen zu
geringfügig schlechteren Ergebnissen.

Kurzfassung englisch:
The Selective Graph Coloring Problem (SGCP) is about finding a subgraph of a particular structure
whose chromatic number is as low as possible. The original graph is divided into several clusters, and
from each cluster the subgraph has to contain exactly one node. This problem is NP-hard and
therefore it is usually solved by means of heuristics.
I implemented several variants of an algorithm making use of Variable Neighborhood Search (VNS) to
search the space of solution candidates and then evaluating the solution using heuristic or exact
methods. Furthermore, each variant can be used with or without a solution archive, i.e. a data
structure in which previously found solutions are stored so that duplicates need not be re-evaluated
but can be efficiently converted into new solutions instead. For exact computation of the chromatic
number integer linear programming was used. To obtain an upper bound a variant of greedy coloring
was used. Another variant of the algorithm also counts the number of conflicts that would appear if
one color less were used. Finally, two methods were implemented to obtain a lower bound:
maximum clique and linear programming using column generation.
The program was tested with various instances from the literature. My algorithm often finished
computation within a very short time, but in general it led to slightly worse results.


Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_221215.pdf


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.