Tomas Balyo

Guangping Li

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.