TY - GEN

T1 - An agent-based algorithm for generalized graph colorings

AU - Bui, Thang N.

AU - Nguyen, Thanh Vu H.

PY - 2006

Y1 - 2006

N2 - This paper presents an algorithm for solving a number of generalized graph coloring problems. Specifically, it gives an agent-based algorithm for the Bandwidth Coloring problem. Using a standard method for preprocessing the input, the same algorithm can also be used to solve the Multicoloring and Bandwidth Multicoloring problems. In the algorithm a number of agents, called ants, each of which colors a portion of the graph, collaborate to obtain a coloring of the entire graph. This coloring is then further improved by a local optimization algorithm. Experimental results on a set of benchmark graphs for these generalized coloring problems show that this algorithm performs very well compared to other heuristic approaches.

AB - This paper presents an algorithm for solving a number of generalized graph coloring problems. Specifically, it gives an agent-based algorithm for the Bandwidth Coloring problem. Using a standard method for preprocessing the input, the same algorithm can also be used to solve the Multicoloring and Bandwidth Multicoloring problems. In the algorithm a number of agents, called ants, each of which colors a portion of the graph, collaborate to obtain a coloring of the entire graph. This coloring is then further improved by a local optimization algorithm. Experimental results on a set of benchmark graphs for these generalized coloring problems show that this algorithm performs very well compared to other heuristic approaches.

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

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

U2 - 10.1145/1143997.1144001

DO - 10.1145/1143997.1144001

M3 - Conference contribution

AN - SCOPUS:33750235578

SN - 1595931864

SN - 9781595931863

T3 - GECCO 2006 - Genetic and Evolutionary Computation Conference

SP - 19

EP - 26

BT - GECCO 2006 - Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery

T2 - 8th Annual Genetic and Evolutionary Computation Conference 2006

Y2 - 8 July 2006 through 12 July 2006

ER -