Coloring large graphs based on independent set extraction

Coloring large graphs based on independent set extraction

0.00 Avg rating0 Votes
Article ID: iaor20116242
Volume: 39
Issue: 2
Start Page Number: 283
End Page Number: 290
Publication Date: Feb 2012
Journal: Computers and Operations Research
Authors: ,
Keywords: sets, heuristics: tabu search
Abstract:

This paper presents an effective approach (EXTRACOL) to coloring large graphs. The proposed approach uses a preprocessing method to extract large independent sets from the graph and a memetic algorithm to color the residual graph. Each preprocessing application identifies, with a dedicated tabu search algorithm, a number of pairwise disjoint independent sets of a given size in order to maximize the vertices removed from the graph. We evaluate EXTRACOL on the 11 largest graphs (with 1000 to 4000 vertices) of the DIMACS challenge benchmarks and show improved results for four very difficult graphs (DSJC1000.9, C2000.5, C2000.9, C4000.5). The behavior of the proposed algorithm is also analyzed.

Reviews

Required fields are marked *. Your email address will not be published.