An ant-based algorithm for coloring graphs

This paper presents an ant-based algorithm for the graph coloring problem. An important difference that distinguishes this algorithm from previous ant algorithms is the manner in which ants are used in the algorithm. Unlike previous ant algorithms where each ant colors the entire graph, each ant in...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2008-01, Vol.156 (2), p.190-200
Main Authors: Bui, Thang N., Nguyen, ThanhVu H., Patel, Chirag M., Phan, Kim-Anh T.
Format: Article
Language:English
Subjects:
Ant-based algorithm
Graph coloring
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents an ant-based algorithm for the graph coloring problem. An important difference that distinguishes this algorithm from previous ant algorithms is the manner in which ants are used in the algorithm. Unlike previous ant algorithms where each ant colors the entire graph, each ant in this algorithm colors just a portion of the graph using only local information. These individual coloring actions by the ants form a coloring of the graph. Even with the lack of pheromone laying capacity by the ants, the algorithm performed well on a set of 119 benchmark graphs. Furthermore, the algorithm produced very consistent results, having very small standard deviations over 50 runs of each graph tested.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2006.07.012