A Novel Exact Algorithm for Graph Coloring via Implicit Enumeration


(*) Corresponding author


Authors' affiliations


DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract


This paper proposes a quick exact algorithm for the graph coloring problem. The algorithm is based on implicit enumerating the coloring sequences of graph and converting the conflict edges constraints into carry numbers, which avoid exponential unnecessary graph coloring sequences testing. Only polynomial memory is needed in our algorithm, and symmetrical coloring solutions obtained by color permutations were removed. The algorithm performs reasonably well on a set of 61 benchmark graphs,
Copyright © 2013 Praise Worthy Prize - All rights reserved.

Keywords


Graph Coloring Problem; Combinatorial Optimization; Implicit Enumeration

Full Text:

PDF


References


D. De Werra, An introduction to timetabling. European Journal of Operational Research, Vol. 19, pp. 151-162, 1985.

L. Bianco, M. Caramia, P. Dell'Olmo, Solving a preemptive scheduling problem using coloring technique, in Ed. Weglarz, Project Scheduling Recent Models, Algorithms and Applications, Kluwer Academic Publishers, 1998.

S. Kannan, T. Proebsting, Register allocation in structured programs. Journal of Algorithms, Vol. 29, pp.223-237, 1998.

D. Brelaz, New methods to color the vertices of a graph. Communications of the ACM, Vol. 22(4), pp.251-256, 1979.

F. T. Leighton, A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards, Vol. 84(6), pp.489-506, 1979.

J. Culberson, F. Luo, Exploring the k-colorable landscape with iterated greedy. cliques, Coloring and Satisfiability - Second DIMACS Implementation Challenge, American Mathematical Society, Vol.26, pp.245-284, 1996.

T. White, B. Pagurek, F. Oppacher, ASGA: Improving the ant system by integration with genetic algorithms. Proceedings of the 3rd Conference on Genetic Programming (GP/SGA 98), Vol.7, pp.610-617, 1998.

C. Morgenstern, Distributed coloration neighborhood search. Cliques, Coloring and Satisfiability - Second DIMACS Implementation Challenge 1993, American Mathematical Society, Vol. 26, pp.335-358, 1996.

A. Hertz, D.Werra, Using tabu search techniques for graph coloring. Computing, Vol.39, pp.345-351, 1987.

F. Comellas, J. Ozon, Graph coloring algorithms for assignment problems in radio networks. Applications of Neural Networks to Telecommunications 2. Edit, pp.49-56, 1995.

D. Costa, A. Hertz, Ants can colour graphs. Journal of Operational Research Society, Vol. 48, pp.295-305, 1997.

C. Lucet, F. Mendes, A. Moukrim, An exact method for graph coloring. Computers and Operations Research, Vol. 33(8), pp.2189-2207, 2006

IM. Diaz,P. Zabala, A branch-and-cut algorithm for graph coloring. Combinatorial Optimization, Vol. 154(5), pp.826-847, 2006

M. Caramia, P. DellOlmo, Iterative coloring extension of a maximum clique, Naval Research Logistics, Vol.48, pp.518-550, 2001.

F. Hermann, A. Hertz, Finding the chromatic number by means of critical graphs, ACM Journal of Experimental Algorithms, Vol.7(10), pp.1-9, 2002.

Igor Dukanovic, Franz Rendl, A semidefinite programming based heuristic for graph coloring. Discrete Applied Mathematics, Vol. 156, pp. 180–189, 2008.

Thang N. Bui, ThanhVu H. Nguyen, Chirag M. Patel and Kim-Anh T. Phan, An ant-based algorithm for coloring graphs. Discrete Applied Mathematics, Vol. 156, pp. 190-200, 2008.

M.A. Mobarhan, A. Shahbahrami, S. Derogar, License Plate Identification Algorithms Using Color Analysis and Edge Features, International Review on Computers and Software,Vol. 7, pp. 1012-1019, 2012.


Refbacks

  • There are currently no refbacks.


Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize