Abstract:
We launch a study on the dynamic form of the graph coloring problem proving it to be
fixed-parameter tractable with respect to the edit-parameter. This leads us to present a
new turbo-charged heuristic for the problem that works by merging standard heuristic
tools like Greedy coloring with the turbo-charging technique. The recently introduced
turbo-charging idea is further enhanced in this thesis by introducing a dynamic version
of turbo-charging where the moment of regret and the rollback points are determined
dynamically. Experiments comparing our turbo-charging algorithm to other heuristics
were conducted on a number of known benchmarks. Our heuristic produced exceptional
results that were often better than all the other available heuristics.
Keywords:
