Geodesic
A New Efficient RLF-Like Algorithm for the Vertex Coloring Problem
Yugoslav journal of operations research, Tome 26 (2016) no. 4, p. 441 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

The Recursive Largest First (RLF) algorithm is one of the most popular greedy heuristics for the vertex coloring problem. It sequentially builds color classes on the basis of greedy choices. In particular, the first vertex placed in a color classC is one with a maximumnumber of uncolored neighbors, and the next vertices placed in C are chosen so that they have as many uncolored neighbors which cannot be placed in C. These greedy choices can have a significant impact on the performance of the algorithm, which explains why we propose alternative selection rules. Computational experiments on 63 difficult DIMACS instances show that the resulting new RLF-like algorithm, when compared with the stan- dard RLF, allows to obtain a reduction of more than 50% of the gap between the number of colors used and the best known upper bound on the chromatic num- ber. The new greedy algorithm even competes with basic metaheuristics for the vertex coloring problem.
Classification : 05C15, 05C85
Keywords: Graph coloring, Greedy algorithm 
@article{YJOR_2016_26_4_a2,
     author = {Mourchid Adegbindin and Alain Hertz and Martine Bella{\"\i}Che},
     title = {A {New} {Efficient} {RLF-Like} {Algorithm} for the {Vertex} {Coloring} {Problem}},
     journal = {Yugoslav journal of operations research},
     pages = {441 },
     year = {2016},
     volume = {26},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2016_26_4_a2/}
}
TY  - JOUR
AU  - Mourchid Adegbindin
AU  - Alain Hertz
AU  - Martine BellaïChe
TI  - A New Efficient RLF-Like Algorithm for the Vertex Coloring Problem
JO  - Yugoslav journal of operations research
PY  - 2016
SP  - 441 
VL  - 26
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/YJOR_2016_26_4_a2/
LA  - en
ID  - YJOR_2016_26_4_a2
ER  - 
%0 Journal Article
%A Mourchid Adegbindin
%A Alain Hertz
%A Martine BellaïChe
%T A New Efficient RLF-Like Algorithm for the Vertex Coloring Problem
%J Yugoslav journal of operations research
%D 2016
%P 441 
%V 26
%N 4
%U http://geodesic.mathdoc.fr/item/YJOR_2016_26_4_a2/
%G en
%F YJOR_2016_26_4_a2
Mourchid Adegbindin; Alain Hertz; Martine BellaïChe. A New Efficient RLF-Like Algorithm for the Vertex Coloring Problem. Yugoslav journal of operations research, Tome 26 (2016) no. 4, p. 441 . http://geodesic.mathdoc.fr/item/YJOR_2016_26_4_a2/