Date: June 1992
University of Alberta Computing Science Technical Report TR92-07
The resulting Iterated Greedy algorithm(IG) can obtain colorings in the range 100 to 103 on graphs in G(1000,1/2). More interestingly, it can optimally color k-colorable graphs with k up to 60 and n=1000, exceeding results of anything in the literature for these graphs. We couple this algorithm with several other coloring algorithms, including a modified Tabu search, and one that tries to find large independent sets using a pruned backtrack. With these combined algorithms we find 86 and 87 colorings for G(1000,1/2). Finally, we explore the areas of difficulty in probabilistic graph space under a natural parameterization. Specifically, we check our system on k-colorable graphs in G(300,p,k) for 0.05<=p<=0.95 and 2<=k<=105. We find a narrow ridge where the algorithms fail to find the specified coloring, but easy success everywhere else.
Keywords: graph coloring algorithms, independent sets, Tabu, random graphs
Full Paper (postscript). It can also be retrieved by anonymous ftp ftp.cs.ualberta.ca pub/TechReports in compressed postscript.
Queries: email to joe@cs.ualberta.ca
Dec. 21, 2000