Parallel tabu search for graph coloring problem

• Autorzy: Dąbrowski J. , Kubale M.
• Konferencja: Evolutionary Computation and Global Optimization 2006 / National Conference (9 ; 31.05-2.06.2006 ; Murzasichle, Poland)
• Języki publikacji: EN

Abstrakty

EN

Tabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of parallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experirnental results are based on graphs available from the DIMACS benchmark suite.

Słowa kluczowe

EN

graph theory; graph coloring; Taboo Search; TS; metaheuristics

PL

teoria grafu; kolorowanie grafu; przeszukiwanie tabu; metaheurystyka

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2006
• Tom: z. 156
• Strony: 87--95
• Opis fizyczny: Bibliogr. 6 poz., tab.

Twórcy

autor

Dąbrowski J.

autor

Kubale M.

• Gdańsk University of Technology, Faculty of Electronics, Telecommunications and Informatics, Gdańsk, Poland,

Bibliografia

• [1] C. Avanthay, A. Hertz and N. Zufferey. Variable neighborhood search for graph coloring. European Journal of Operational Research, 151:379-388, 2003.
• [2] D. Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22:251-256, 1979.
• [3] T.G. Crainic, M. Toulouse and M. Gendreau. Towards a taxonomy of parallel tabu search heuristics. INFORMS Journal of Computing, 9:61-72, 1997.
• [4] P. Galinier and J.-K. Hao. Hybrid evolutionary algorithm for graph coloring. Journal of Combinatorial Optimization, 3:379-397, 1999.
• [5] A. Hertz and D. de Werra. Using tabu search techniques for graph coloring. Computing, 39:345-351, 1987.
• [6] A. Johri and D.W. Matula. Probabilistic bounds and heuristic algorithms for coloring large random graphs. Technical report, Southern Methodist University, 1982.