Solving the graph coloring problem via hybrid genetic algorithms

被引：12

作者：

Douiri, Sidi Mohamed ^{[1
]}

Elbernoussi, Souad ^{[1
]}

机构：

[1] University Mohammed V, Faculty of Sciences-Agdal, Rabat

来源：

Journal of King Saud University - Engineering Sciences | 2015年 / 27卷 / 01期

关键词：

DBG heuristic; Genetic algorithm; Graph coloring problem;

D O I：

10.1016/j.jksues.2013.04.001

中图分类号：

学科分类号：

摘要：

Let G = (V,E) an undirected graph, V corresponds to the set of vertices and E corresponds to the set of edges, we focus on the graph coloring problem (GCP), which consist to associate a color to each vertex so that two vertices connected do not possess the same color. In this paper we propose a new hybrid genetic algorithm based on a local search heuristic called DBG to give approximate values of χ(G) for GCP. The proposed algorithm is evaluated on the DIMACS benchmarks and numerical results show that the proposed approach achieves highly competitive results, compared with best existing algorithms. © 2014

引用

页码：114 / 118

页数：4

共 29 条

[1]

Avanthay C., Hertz A., Zufferey N., A variable neighbourhood search for graph coloring, Eur. J. Oper. Res., 151, 2, pp. 379-388, (2003)

[2]

Barnier N., Brisset P., Graph coloring for air traffic flow management, pp. 133-147, (2002)

[3]

Blochliger I., Zufferey N., A graph coloring heuristic using partial solutions and a reactive tabu scheme, Comput. Oper. Res., 35, 3, pp. 960-975, (2008)

[4]

Brelaz D., New methods to color the vertices of a graph, Commun. ACM, 22, 4, pp. 251-256, (1979)

[5]

Burke E.K., Elliman D.G., Weare R.F., A university timetabling system based on graph colouring and constraint manipulation, J. Res. Comput. Educ., 27, 1, pp. 1-18, (1994)

[6]

Chams M., Hertz A., de Werra D., Some experiments with simulated annealing for coloring graphs, Eur. J. Oper. Res., 132, 2, pp. 260-266, (1987)

[7]

Chiarandini M., Stutzle T., An application of iterated local search to graph coloring, Johnson, pp. 112-125, (2002)

[8]

Davis L., Order-based genetic algorithms and the graph coloring problem, Handbook of Genetic Algorithms, pp. 72-90, (1991)

[9]

de Werra D., An introduction to timetabling, Eur. J. Oper. Res., 19, 2, pp. 151-162, (1985)

[10]

Dorne R., Hao J.K., tabu search for graph coloring, t-colorings and set t-colorings metaheuristics, Adv. Trends Local Search Paradigms Optim., 117, pp. 77-92, (1998)

← 1 2 3 →