An agent-based algorithm for generalized graph colorings

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An agent-based algorithm for generalized graph colorings

Full text

Pdf (153 KB)

Source

Genetic And Evolutionary Computation Conference archive
Proceedings of the 8th annual conference on Genetic and evolutionary computation table of contents

Seattle, Washington, USA

SESSION: Ant colony optimization and swarm intelligence: papers table of contents

Pages: 19 - 26

Year of Publication: 2006

ISBN:1-59593-186-4

Authors

Thang N. Bui	The Pennsylvania State University at Harrisburg, Middletown, PA
ThanhVu H. Nguyen	The Pennsylvania State University at Harrisburg, Middletown, PA

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 130, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1143997.1144001 What is a DOI?

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Abril, J., F. Comellas, A. Cortes, J. Ozon, and M. Vaquer, "A Multi-Agent System for Frequency Assignment in Cellular Radio Networks," IEEE Trans. on Vehicular Technology, 49(5), September 2000, pp. 1558--1564.
	2	Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
	3	Avrim Blum , David Karger, An Õ(n3/14)-coloring algorithm for 3-colorable graphs, Information Processing Letters, v.61 n.1, p.49-53, Jan. 14, 1997 [doi>10.1016/S0020-0190(96)00190-1 ]
	4	Bonabeau, E., M. Dorigo, and G. Theraulaz, "Inspiration for Optimization from Social Insect Behavior," Nature, 406, July 6, 2000, pp. 39--42.
	5	Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
	6	Bui, T. N. and C. Patel, "An Ant system Algorithm for Coloring Graphs," Computational Symposium on Graph Coloring and Its Generalizations, COLOR02, Cornell University, Ithaca, NY, 2002.
	7	Chiarandini, M. and T. Stützle, "An Application of Iterated Local Search to Graph Coloring Problem," Computational Symposium on Graph Coloring and Its Generalizations, COLOR02, Cornell University, Ithaca, NY, 2002.
	8	Comellas, F. and J. Ozon, "Graph Coloring Algorithms for Assignment Problems in Radio Networks," Applications of Neural Networks to Telecommunications 2, 1995, pp. 49--56.
	9	Comellas, F. and J. Ozon, "An Ant Algorithm for the Graph Coloring Problem," ANTS'98 - From Ant Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization, Brussels, Belgium, October 15--16, 1998.
	10	Computational Series: Graph Coloring and Its Generalizations. "http://mat.gsia.cmu.edu/COLOR04".
	11	Costa, D. and A. Hertz, "Ants Can Colour Graphs," Journal of Operational Research Society, 48, 1997, pp. 295--305.
	12	Culberson J. and F. Luo, "Exploring the k-Colorable Landscape with Iterated Greedy," Cliques, Coloring and Satisfiability - Second DIMACS Implementation Challenge 1993, American Mathematical Society, 26, 1996, pp. 245--284.
	13	Marco Dorigo , Gianni Di Caro, The ant colony optimization meta-heuristic, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
	14	Dorigo, M. and L. Gambardella, "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem," IEEE Trans. on Evolutionary Computation, 1(1), 1997, pp. 53--66.
	15	Fleurent, C. and J. Ferland, "Genetic and Hybrid Algorithms for Graph Coloring," Annals of Operations Research, 63, 1996, pp. 437--461.
	16	Magnús M. Hallórsson, A still better performance guarantee for approximate graph coloring, Information Processing Letters, v.45 n.1, p.19-23, Jan. 25, 1993 [doi>10.1016/0020-0190(93)90246-6 ]
	17	A. Hertz , D. de Werra, Using tabu search techniques for graph coloring, Computing, v.39 n.4, p.345-351, Dec. 1987 [doi>10.1007/BF02239976]
	18	Jin, M., H. Wu, J. Horng, and C. Tsai, "An Evolutionary Approach to Fixed Channel Assignment Problems with Limited Bandwidth," Proc. of IEEE International Conference on Communications, 7, 2001, pp. 2100--2104.
	19	David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning, Operations Research, v.39 n.3, p.378-406, May-June 1991
	20	David J. Johnson , Michael A. Trick, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993, American Mathematical Society, Boston, MA, 1996
	21	Joslin, D. E. and D. P. Clements, "Squeaky Wheel Optimization," Journal of Artificial Intelligence Research, 10, 1999, pp. 353--373.
	22	Leighton, F. T. "A Graph Coloring Algorithm for Large Scheduling Problems," J. of Research of the National Bureau of Standards, 84(6), 1979, pp. 489--506.
	23	Lim, A., X. Zhang, and Y. Zhu, "A Hybrid Method for the Graph Coloring Problem and Its Generalizations," 5th Metaheuristics International Conference, 2003.
	24	A. Lim , Y. Zhu , Q. Lou , B. Rodrigues, Heuristic methods for graph coloring problems, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066892]
	25	Maniezzo, V. and A. Carbonaro, "Ant Colony Optimization: An Overview," it Essays and Surveys in Metaheuristics, C. Ribeiro editor, Kluwer Academic Publishers, 2001, pp. 21--44.
	26	Morgenstern, C., "Distributed Coloration Neighborhood Search," Cliques, Coloring and Satisfiability - Second DIMACS Implementation Challenge 1993, American Mathematical Society, 26, 1996, pp. 335--358.
	27	Eun-Jong Park , Yong-Hyuk Kim , Byung Ro Moon, Genetic Search For Fixed Channel Assignment Problem With Limited Bandwidth, Proceedings of the Genetic and Evolutionary Computation Conference, p.1172-1179, July 09-13, 2002
	28	Phan, V. and S. Skiena, "Coloring Graphs with a General Heuristic Search Engine," Computational Symposium on Graph Coloring and Its Generalizations, COLOR02, Cornell University, Ithaca, NY, 2002.
	29	Prestwich, S. D. "Constrained Bandwidth Multicoloration Neighborhoods," Computational Symposium on Graph Coloring and Its Generalizations, COLOR02, Cornell University, Ithaca, NY, 2002.
	30	White, T. B. Pagurek, and F. Oppacher, "ASGA: Improving the Ant System by Integration with Genetic Algorithms," Proc. of the 3rd Conference on Genetic Programming, July 1998, pp. 610--617.