<  Back to the Polytechnique Montréal portal

A new efficient RLF-like algorithm for the vertex coloring problem

Mourchid Adegbindin, Alain Hertz and Martine Bellaïche

Article (2016)

[img]
Preview
Published Version
Terms of Use: Creative Commons Attribution Non-commercial Share Alike.
Download (570kB)
Cite this document: Adegbindin, M., Hertz, A. & Bellaïche, M. (2016). A new efficient RLF-like algorithm for the vertex coloring problem. Yugoslav Journal of Operations Research, 26(4), p. 441-456. doi:10.2298/yjor151102003a
Show abstract Hide abstract

Abstract

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 class C is one with a maximum number 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 standard 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 number. The new greedy algorithm even competes with basic metaheuristics for the vertex coloring problem.

Uncontrolled Keywords

Graph coloring, Greedy algorithm.

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2700 Technologie de l'information
2700 Technologie de l'information > 2713 Algorithmes
2700 Technologie de l'information > 2717 Études de modélisation et de simulation
2950 Mathématiques appliquées > 2956 Optimisation et théories de commande optimale
Department: Département de génie informatique et génie logiciel
Département de mathématiques et de génie industriel
Research Center: Non applicable
Date Deposited: 10 Mar 2020 10:32
Last Modified: 11 Mar 2020 01:20
PolyPublie URL: https://publications.polymtl.ca/3601/
Document issued by the official publisher
Journal Title: Yugoslav Journal of Operations Research (vol. 26, no. 4)
Publisher: Faculty of Organizational Sciences, Belgrade, Mihajlo Pupin Institute, Belgrade, Faculty of Transport and Traffic Engineering, Belgrade, Faculty of Mining and Geology – Department of Mining, Belgrade, Mathematical Institute SANU, Belgrade
Official URL: https://doi.org/10.2298/yjor151102003a

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Dimensions

Repository Staff Only