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 -