Institut für Theoretische Informatik, Algorithm Engineering

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.