Home | deutsch  | Legals | Sitemap | KIT

Solving the Graph Coloring Problem with Cooperative Local Search

Solving the Graph Coloring Problem with Cooperative Local Search
Subject:Cooperative Local Search
Type:Bachelorarbeit
Supervisor:

Tomas Balyo

Student:

Guangping Li

Links:Links_bearbeiten

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.