Colour Reassignment in Tabu Search for the Graph Set T-Colouring Problem

  • Marco Chiarandini
  • Thomas Stützle
  • Kim S. Larsen
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4030)


The graph set T-colouring problem (GSTCP) is a generalisation of the classical graph colouring problem and it is used to model, for example, the assignment of frequencies in mobile networks. The GSTCP asks for the assignment of sets of nonnegative integers to the vertices of a graph so that constraints on the separation of any two numbers assigned to a single vertex or to adjacent vertices are satisfied and some objective function is optimised. Among the various objective functions of interest, we focus on the minimisation of the span, that is, the difference between the largest and the smallest integers used.

In practical applications large size instances of the GSTCP are to be solved and heuristic algorithms become necessary. In this article, we propose a new hybrid procedure for the solution of the GSTCP that combines a known tabu search algorithm with an algorithm for the enumeration of all feasible re-assignments of colours to a vertex. We compare the new algorithm with the basic tabu search algorithm and for both we study possible variants. The experimental comparison, supported by statistical analysis, establishes that the new hybrid algorithm performs better on a variety of instance classes.


Tabu Search Adjacent Vertex Graph Colouring Edge Density Colour Assignment 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Jensen, T.R., Toft, B.: Graph coloring problems. Wiley Interscience, New York (1995)zbMATHGoogle Scholar
  2. 2.
    Hale, W.K.: Frequency assignment: Theory and applications. Proceedings of the IEEE 68, 1497–1514 (1980)CrossRefGoogle Scholar
  3. 3.
    Tesman, B.A.: Set T-colorings. Congressus Numerantium 77, 229–242 (1990)zbMATHMathSciNetGoogle Scholar
  4. 4.
    Roberts, F.S.: T-colorings of graphs: Recent results and open problems. Discrete Mathematics 93, 229–245 (1991)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Tesman, B.A.: List T-colorings. Discrete Applied Mathematics 45, 277–289 (1993)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Giaro, K., Janczewski, R., Malafiejski, M.: The complexity of the T-coloring problem for graphs with small degree. Discrete Applied Mathematics 129, 361–369 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Eisenblätter, A., Grötschel, M., Koster, A.M.C.A.: Frequency assignment and ramifications of coloring. Discussiones Mathematicae Graph Theory 22, 51–88 (2002)zbMATHMathSciNetGoogle Scholar
  8. 8.
    Aardal, K.I., van Hoesel, C.P.M., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for the frequency assignment problem. ZIB-report 01–40, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Germany (2001)Google Scholar
  9. 9.
    Hoos, H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufmann Publishers, San Francisco (2004)Google Scholar
  10. 10.
    Dorne, R., Hao, J.: Tabu search for graph coloring, T-colorings and set T-colorings. In: Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 77–92. Kluwer Academic Publishers, Dordrecht (1998)Google Scholar
  11. 11.
    Phan, V., Skiena, S.: Coloring graphs with a general heuristic search engine. In: Johnson, D.S., Mehrotra, A., Trick, M. (eds.) Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, Ithaca, New York, USA, pp. 92–99 (2002)Google Scholar
  12. 12.
    Prestwich, S.: Hybrid local search on two multicolouring models. In: International Symposium on Mathematical Programming, Copenhagen, Denmark (2003)Google Scholar
  13. 13.
    Lim, A., Zhu, Y., Lou, Q., Rodrigues, B.: Heuristic methods for graph coloring problems. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 933–939. Springer, Heidelberg (2006)Google Scholar
  14. 14.
    Culberson, J., Beacham, A., Papp, D.: Hiding our colors. In: Montanari, U., Rossi, F. (eds.) CP 1995. LNCS, vol. 976, pp. 31–42. Springer, Heidelberg (1995)Google Scholar
  15. 15.
    Anderson, L.G.: A simulation study of some dynamic channel assignment algorithms in a high capacity mobile telecommunications system. IEEE Transactions on Communications 21, 1294–1301 (1973)CrossRefGoogle Scholar
  16. 16.
    Chiarandini, M.: Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems. PhD thesis, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany (2005)Google Scholar
  17. 17.
    Hurley, S., Smith, D.H., Thiel, S.U.: FASoft: A system for discrete channel frequency assignment. Radio Science 32, 1921–1939 (1997)CrossRefGoogle Scholar
  18. 18.
    Fleurent, C., Ferland, J.: Genetic and hybrid algorithms for graph coloring. Annals of Operations Research 63, 437–464 (1996)zbMATHCrossRefGoogle Scholar
  19. 19.
    Galinier, P., Hao, J.: Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization 3, 379–397 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  20. 20.
    Costa, D.: On the use of some known methods for T-colorings of graphs. Annals of Operations Research 41, 343–358 (1993)zbMATHCrossRefGoogle Scholar
  21. 21.
    Castelino, D., Hurley, S., Stephens, N.: A tabu search algorithm for frequency assignment. Annals of Operations Research 63, 301–320 (1996)zbMATHCrossRefGoogle Scholar
  22. 22.
    Hao, J.K., Dorne, R., Galinier, P.: Tabu search for frequency assignment in mobile radio networks. Journal of Heuristics 4, 47–62 (1998)zbMATHCrossRefGoogle Scholar
  23. 23.
    Hao, J.K., Perrier, L.: Tabu search for the frequency assignment problem in cellular radio networks. Technical Report LGI2P, EMA-EERIE, Parc Scientifique Georges Besse, Nimes, France (1999)Google Scholar
  24. 24.
    Birattari, M.: The race package for R. Racing methods for the selection of the best. Technical Report TR/IRIDIA/2003-37, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium (2003)Google Scholar
  25. 25.
    Conover, W.: Practical Nonparametric Statistics. John Wiley & Sons, New York (1999)Google Scholar
  26. 26.
    Chiarandini, M., Basso, D., Stützle, T.: Statistical methods for the comparison of stochastic optimizers. In: Doerner, K.F., et al. (eds.) MIC 2005: The Sixth Metaheuristics International Conference, Vienna, Austria, pp. 189–196 (2005)Google Scholar
  27. 27.
    Matsui, S., Tokoro, K.: Improving the performance of a genetic algorithm for minimum span frequency assignment problem with an adaptive mutation rate and a new initialization method. In: Proc. of GECCO-2001 (Genetic and Evolutionary Computation Conference), pp. 1359–1366. Morgan Kaufmann Publishers, San Francisco (2001)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Marco Chiarandini
    • 1
  • Thomas Stützle
    • 2
  • Kim S. Larsen
    • 1
  1. 1.IMADAUniversity of Southern DenmarkOdenseDenmark
  2. 2.CoDe, IRIDIAUniversité Libre de BruxellesBrusselsBelgium

Personalised recommendations