Month: June 2017

The program uses the improved tabu search from: Galinier and Hao (1999): “Hybrid evolutionary algorithms for graph coloring” . For maximum variability in the colorings, it starts each time with a random 500-coloring of the 500-vertex graph. Starting from a valid k-coloring, a (k-1)-coloring, not necessarily valid, is obtained by distributing the elements of one… Continue reading newtabuzz99a.c for DIMACS graph DSJC500.5.col

This is my best effort at implementing Galinier and Hao’s Tabu Search algoritm from their 1999 paper: “Hybrid Evolutionary Algorithms for Graph Coloring”. It produces 50-colorings of DSJC500.5.col after a few hours. Filename:   newtabuzf99a.c   #include <stdio.h> #include <stdlib.h> #include <math.h> #define MAX_VERTEX 1000 #define MAX_COLORS 500 int adj_mat[MAX_VERTEX][MAX_VERTEX]; int Gamma[MAX_VERTEX][MAX_COLORS]; int Fast_Gamma[MAX_VERTEX][MAX_COLORS]; int tabu_list[MAX_VERTEX][MAX_COLORS];… Continue reading newtabuzf99a.c for DIMACS DSJC500.5.col