Abstract
We present a Tabu Search (TS) method that employs a simple version of ejection chains for coloring graphs. The procedure is tested on a set of benchmark problems. Empirical results indicate that the proposed TS implementation outperforms other metaheuristic methods, including Simulated Annealing, a previous version of Tabu Search and a recent implementation of a Greedy Randomized Adaptive Search Procedure (GRASP).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Chams, A. Hertz and D. deWerra, Some experiments with simulated annealing for coloring graphs, European Journal of Operational Research 32 (1987) 260–266.
U. Dorndorf and E. Pesch, Fast clustering algorithms, ORSA Journal on Computing 6 (1994) 141–153.
R. Dorne and J.-K. Hao, Tabu Search for graph coloring, T-coloring and set T-colorings, in: Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, eds. S. Voß, S. Martello, I. Osman and C. Roucairol (Kluwer, Boston, 1999) pp. 33–47.
T.A.R.E. Feo and M.G.C. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters 8 (1989) 67–71.
T.A.R.E. Feo and M.G.C. Resende, Greedy randomized adaptive search procedures, Journal of Global Optimization 2 (1995) 1–27.
C. Fleurent and J.A. Ferland, Genetic and hybrid algorithms for graph coloring, Annals of Operation Research 63 (1996) 437–464.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness (Freeman, San Francisco, CA, 1979).
F. Glover and M. Laguna, Tabu Search (Kluwer Academic, Dordrecht, 1997).
A. Hertz and D. de Werra, Using Tabu Search techniques for graph coloring, Computing 39 (1988) 345–351.
J.H. Holland, Adaptation in Natural and Artificial Systems (Michigan University Press, Ann Arbor, MI, 1975).
D.S. Johnson, Worst-case behavior of graph coloring algorithms, in: Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica Publishing, Winnipeg, Canada (1974) pp. 513–528.
D.S. Johnson, C.A. Aragon, L.A. Mcgeoch and C. Schevon, Optimization by simulated annealing: an experimental evaluation - part II (graph coloring and number partitioning), Operations Research 31 (1991) 378–406.
S. Kirkpatrick, C.D. Gelatt, Jr. and M.P. Vecchi, Optimization by simulated annealing, Science 220 (1983) 671–680.
M. Laguna, J.P. Kelly, J.L. González-Velarde and F. Glover, Tabu search for the multilevel generalized assignment problem, European Journal of Operational Research 42 (1995) 677–687.
M. Laguna and R. Martí A GRASP for coloring sparse graphs, Computational Optimization and Applications 19(2) (2001) 165–178.
F.T. Leighton, A graph coloring algorithm for large scheduling problems, J. Res. Nat. Bur. Standards 84 (1979) 489–506.
E. Pesch and F. Glover, TSP ejection chains, Discrete Applied Mathematics 76 (1997) 165–181.
C. Rego and C. Roucairol, A parallel tabu search algorithm using ejection chains for the vehicle routing problem, in: Meta-Heuristics: Theory and Applications, eds. I.H. Osman and J.P. Kelly (Kluwer Academic, Dordrecht, 1996) pp. 661–675.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
González-Velarde, J.L., Laguna, M. Tabu Search with Simple Ejection Chains for Coloring Graphs. Annals of Operations Research 117, 165–174 (2002). https://doi.org/10.1023/A:1021573507189
Issue Date:
DOI: https://doi.org/10.1023/A:1021573507189