Home | english  | Impressum | Sitemap | KIT

Solving the Graph Coloring Problem with Cooperative Local Search

Solving the Graph Coloring Problem with Cooperative Local Search
Forschungsthema:Cooperative Local Search
Typ:Bachelorarbeit
Datum:10.1.2017
Betreuer:

Tomas Balyo

Bearbeiter:

Guangping Li

Links:PDF

Tabucol is a local search algorithm to determine whether the vertices of an undi-
rected graph can be colored with k colors, such that no two vertices connected by an
edge have the same color. This thesis presents an algorithm that solves the graph
coloring problem with parallel Tabucol searches. A hypothesis was experimentally
evaluated that sharing information among the agents will improve the performance
of the parallel search. In this paper, we introduce a new matrix data structure,
which counts the repeated times of one change. This statistic matrix can help rec-
ognizing long-term cycling in the local search. The sharing of this matrix among
the agents can bring further improvement to our algorithm.