Using tabu search techniques for graph coloring. (English) Zbl 0626.68051

Tabu search techniques are used for moving step by step towards the minimum value of a function. A tabu list of forbidden movements is updated during the iterations to avoid cycling and being trapped in local minima. Such techniques are adapted to graph coloring problems. We show that they provide almost optimal colorings of graphs having up to 1000 nodes and their efficiency is shown to be significantly superior to the famous simulated annealing.


68R10 Graph theory (including graph drawing) in computer science
05-04 Software, source code, etc. for problems pertaining to combinatorics
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Bollobàs, B., Thomason, A.: Random graphs of small order. Random graphs ’83. Annals of Discrete Mathematics28, 47–97 (1985). · Zbl 0588.05040
[2] Chams, M., Hertz, A., de Werra, D.: Some experiments with simulated annealing for coloring graphs. EJOR32, 260–266 (1987). · Zbl 0626.90067 · doi:10.1016/S0377-2217(87)80148-0
[3] Glover, F.: Future paths for integer programming and links to artificial intelligence. CAAI Report 85-8, University of Colorado, Boulder CO (1985). · Zbl 0615.90083
[4] Glover, F., McMillan, C., Novick, B.: Interactive decision software and computer graphics for architectural and space planning. Annals of Operations Research5, 557–573 (1985). · doi:10.1007/BF02023611
[5] Johri, A., Matula, D. W.: Probabilistic bounds and heuristic algorithm, for coloring large random graphs. Southern Methodist University, Dallas, Texas (1982).
[6] Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A.: Equation of state calculations by fast computing machines. J. Chem. Phys.21, 1087–1092 (1953). · doi:10.1063/1.1699114
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.