EXTRACOL
Coloring large graphs based on independent set extraction We present an effective approach ({ssf 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 {ssf EXTRACOL} on the 11 largest graphs (with 1000 to 4000 vertices) of the {ssf 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.
This software is also peer reviewed by journal TOMS.
This software is also peer reviewed by journal TOMS.
Keywords for this software
References in zbMATH (referenced in 9 articles , 1 standard article )
Showing results 1 to 9 of 9.
Sorted by year (- Lin, Weibo; Xiao, Mingyu; Zhou, Yi; Guo, Zhenyu: Computing lower bounds for minimum sum coloring and optimum cost chromatic partition (2019)
- Fazli, MohammadAmin; Ghazimatin, Azin; Habibi, Jafar; Haghshenas, Hamid: Team selection for prediction tasks (2016)
- Wu, Qinghua; Hao, Jin-Kao: A review on algorithms for maximum clique problems (2015)
- Zhou, Zhaoyang; Li, Chu-Min; Huang, Chong; Xu, Ruchu: An exact algorithm with learning for the graph coloring problem (2014)
- Wu, Qinghua; Hao, Jin-Kao: An adaptive multistart tabu search approach to solve the maximum clique problem (2013)
- Hao, Jin-Kao; Wu, Qinghua: Improving the extraction and expansion method for large graph coloring (2012)
- Held, Stephan; Cook, William; Sewell, Edward C.: Maximum-weight stable sets and safe lower bounds for graph coloring (2012)
- Wu, Qinghua; Hao, Jin-Kao: An effective heuristic algorithm for sum coloring of graphs (2012)
- Wu, Qinghua; Hao, Jin-Kao: Coloring large graphs based on independent set extraction (2012)