An ant-based algorithm for coloring graphs

Thang N. Bui; Thanh Vu H. Nguyen; Chirag M. Patel; Kim Anh T. Phan

doi:10.1016/j.dam.2006.07.012

An ant-based algorithm for coloring graphs

Thang N. Bui, Thanh Vu H. Nguyen, Chirag M. Patel, Kim Anh T. Phan

School of Science, Engineering & Technology (Harrisburg)

Research output: Contribution to journal › Article › peer-review

66 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	190-200
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	156
Issue number	2
DOIs	https://doi.org/10.1016/j.dam.2006.07.012
State	Published - Jan 15 2008

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2006.07.012

Cite this

@article{33afaa92939b4cf49ffebd04f0a37b88,

title = "An ant-based algorithm for coloring graphs",

abstract = "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.",

author = "Bui, {Thang N.} and Nguyen, {Thanh Vu H.} and Patel, {Chirag M.} and Phan, {Kim Anh T.}",

year = "2008",

month = jan,

day = "15",

doi = "10.1016/j.dam.2006.07.012",

language = "English (US)",

volume = "156",

pages = "190--200",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - An ant-based algorithm for coloring graphs

AU - Bui, Thang N.

AU - Nguyen, Thanh Vu H.

AU - Patel, Chirag M.

AU - Phan, Kim Anh T.

PY - 2008/1/15

Y1 - 2008/1/15

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=37149033990&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=37149033990&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2006.07.012

DO - 10.1016/j.dam.2006.07.012

M3 - Article

AN - SCOPUS:37149033990

SN - 0166-218X

VL - 156

SP - 190

EP - 200

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

ER -

An ant-based algorithm for coloring graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this