Institute of Theoretical Informatics, Algorithmics II

Solving the Graph Coloring Problem with Cooperative Local Search

  • Subject:Cooperative Local Search
  • Type:Bachelorarbeit
  • Supervisor:

    Tomas Balyo

  • Student:

    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.