A new efficient RLF-like algorithm for the vertex coloring problem
DOI:
https://doi.org/10.2298/YJOR151102003AKeywords:
Graph coloring, Greedy algorithmAbstract
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.References
Brélaz, D., “New methods to color the vertices of a graph”, Communications of the ACM, 22 (1979) 251–256.
Brown, J.R., “Chromatic scheduling and the chromatic number problem”, Management Science, 19 (1972) 456–463.
Chams, M., Hertz, A., de Werra, D., “Some experiments with simulated annealing for coloring graphs”, European Journal of Operational Research, 32 (1987) 260–266.
Garey, M., Johnson, D.S., Computer and Intractability, Freeman, San Francisco, 1979.
Chiarandini, M., Galbiati, G., Gualandi, S., “Efficiency issues in the RLF heuristic for graph coloring”, Proceedings of the IX Metaheuristics International Conference, (MIC 2011), July 2011, Udine, Italy, 461–469.
Chiarandini, M., Gualandi, S., http://www.imada.sdu.dk/marcogcp
Chiarandini, M., Stuetzle, T., “An analysis of heuristics for vertex colouring”, Lecture Notes in Computer Science, 6049 (2010) 326–337.
Galinier, P., Hertz, A., Zufferey, N., “An adaptive Memory Algorithm for the k-Colouring Problem”, Discrete Applied Mathematics, 156 (2008) 267–279.
Gualandi, S., Malucelli, F., “Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation”, INFORMS Journal on Computing, 24 (2012) 81–100.
Halldórsson, M., “A still better performance guarantee for approximate graph coloring”, Information Processing Letters, 45 (1993) 19–23.
Held, S., Cook, W., Sewell, E.C., “Maximum-weight stable sets and safe lower bounds for graph coloring”, Mathematical Programming Computation, 4 (2012) 363–381.
Herrmann, F., Hertz, A., “Finding the chromatic number by means of critical graphs”, ACM Journal of Experimental Algorithmics, 7 (2002) 1–9.
Hertz, A., de Werra, D., “Using tabu search techniques for graph coloring”, Computing, 39 (1987) 345–351.
Johnson, D.S., Aragon, C.R., McGeoch, L.A., Shevon, C., “Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning”, Operations Research, 39 (1991) 378–406.
Kubale, M., Jackowski, B., “A generalized implicit enumeration algorithm for graph coloring”, Communications of the ACM, 28 (1985) 412–418.
Leighton, F.T., “A graph coloring algorithm for large scheduling problems”, Journal of Research of the National Bureau of Standards, 84 (1979) 489–503.
Malaguti, E., Monaci, M., Toth, P., “An Exact Approach for the Vertex Coloring Problem”, Discrete Optimization, 8 (2) (2011) 174–190.
Mehrotra, A., Trick, M.A., “A column generation approach for exact graph coloring”, INFORMS Journal on Computing, 8 (1996) 344–354.
Peemöller, J., “A correction to Brélaz’s modification of Brown’s coloring algorithm”, Communications of the ACM, 26 (1983) 593–597.
Trick, M.A., http://mat.gsia.cmu.edu/COLOR/color.html
Downloads
Published
Issue
Section
License
Copyright (c) 2016 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
