Title: Two hybrid ant algorithms for the general T-colouring problem

Authors: Mahmoudi Aicha, Bessedik Malika, Drias Habiba

Addresses: Ecole Superieure de formation en Informatique, BP 68M, 16270, Oued Smar, Algeria. ' Ecole Superieure de formation en Informatique, BP 68M, 16270, Oued Smar, Algeria. ' Ecole Superieure de formation en Informatique, BP 68M, 16270, Oued Smar, Algeria

Abstract: GCP is a well-known combinatorial problem that admits several generalisations from which the T-colouring (GTCP). Given a graph G and sets T of positive integers associated to the edges of G, a T-colouring of G is an assignment of colours to its vertices so the assigned colours distances do not exist in the associated set T. Since this problem is NP-Complete, only few heuristics are implemented for restricted conditions on the sets T. The ant colony optimisation (ACO) has been successfully applied to different problems [SAL08]. Nevertheless, no attempt of ACO has been published for the T-colouring problem. We introduce, in this paper, two hybrid evolutionary approaches combining an ACO algorithm and a tabu search for the GTCP. These approaches are experimented for the general and restricted cases of the GTCP with different parameter|s settings. The results are encouraging and show often better results than those published.

Keywords: T-colouring; metaheuristics; tabu search; ant colony optimisation; ACO; span; graph colouring problem; bio-inspired computation.

DOI: 10.1504/IJBIC.2010.036162

International Journal of Bio-Inspired Computation, 2010 Vol.2 No.5, pp.353 - 362

Published online: 25 Oct 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article