<  Retour au portail Polytechnique Montréal

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

Mourchid Adegbindin, Alain Hertz et Martine Bellaïche

Article de revue (2016)

Document en libre accès dans PolyPublie et chez l'éditeur officiel
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Version officielle de l'éditeur
Conditions d'utilisation: Creative Commons: Attribution-Pas d'utilisation commerciale-Partage dans les mêmes conditions (CC BY-NC-SA)
Télécharger (477kB)
Afficher le résumé
Cacher le résumé

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.

Mots clés

Graph coloring, Greedy algorithm.

Sujet(s): 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
Département: Département de génie informatique et génie logiciel
Département de mathématiques et de génie industriel
URL de PolyPublie: https://publications.polymtl.ca/3601/
Titre de la revue: Yugoslav Journal of Operations Research (vol. 26, no 4)
Maison d'édition: 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
DOI: 10.2298/yjor151102003a
URL officielle: https://doi.org/10.2298/yjor151102003a
Date du dépôt: 10 mars 2020 10:32
Dernière modification: 11 mai 2023 04:12
Citer en APA 7: 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), 441-456. https://doi.org/10.2298/yjor151102003a

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Dimensions

Actions réservées au personnel

Afficher document Afficher document