A Metaheuristic Approach for the Vertex Coloring Problem

References

• Blöchliger I., Zufferey N. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. (2008) 35:960–975Crossref, Google Scholar
• Bollobàs B., Thomason A. Random graphs of small order. Ann. Discrete Math. (1985) 28:47–97Google Scholar
• Brèlaz D. New methods to color the vertices of a graph. Comm. ACM (1979) 22:251–256Crossref, Google Scholar
• Caprara A., Fischetti M., Toth P. A heuristic method for the set covering problem. Oper. Res. (1999) 47:730–743Link, Google Scholar
• Caramia M., Dell'Olmo P., Vitter J. S., Zaroliagis C. D. A fast and simple local search for graph coloring. Proc. 3rd Workshop on Algorithm Engrg. WAE'99, Lecture Notes in Computer Science (1999) (Springer-Verlag, Berlin) 319–313Crossref, Google Scholar
• Chow F. C., Hennessy J. L. The priority-based coloring approach to register allocation. ACM Trans. Programming Languages Systems (1990) 12:501–536Crossref, Google Scholar
• Culberson J. C., Luo F., Johnson D. S., Trick M. A. Exploring the k-colorable landscape with iterated greedy. Cliques, Coloring, and Satisfiability: 2nd DIMACS Implementation Challenge, 1993 (1996) (American Mathematical Society, Providence, RI) 245–284DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• Davis L.Handbook of Genetic Algorithms (1998) (Van Nostrand Reinhold, New York) Google Scholar
• de Werra D. An introduction to timetabling. Eur. J. Oper. Res. (1985) 19:151–162Crossref, Google Scholar
• Diaz I. M., Zabala P., Johnson D. S., Mehrotra A., Trick M. A branch and cut algorithm for graph coloring. Proc. Computational Sympos. Graph Coloring and Its Generalization (2002) Ithaca, NY:55–62Google Scholar
• Dongarra J. J. Performance of various computers using standard linear equations software (linpack benchmark report). (2006) . Technical Report CS-89-85, Computer Science Department, University of Tennessee, KnoxvilleGoogle Scholar
• Dorne R., Hao J. K., Voss S., Martello S., Osman I. H., Roucairol C. Tabu search for graph coloring, t-coloring and set t-colorings. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1998) (Kluwer Academic Publishers, Boston) 77–92Google Scholar
• Fleurent C., Ferland J. A., Johnson D. S., Trick M. A. Object-oriented implementation of heuristic search methods for graph coloring. Cliques, Coloring, and Satisfiability: 2nd DIMACS Implementation Challenge, 1993 (1996) (American Mathematical Society, Providence, RI) 619–652DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• Funabiki N., Higashino T. A minimal-state processing search algorithm for graph coloring problems. IEICE Trans. Fundamentals (2000) E83-A:1420–1430Google Scholar
• Galinier P., Hao J. K. Hybrid evolutionary algorithms for graph coloring. J. Combin. Optim. (1999) 3:379–397Crossref, Google Scholar
• Gamst A. Some lower bounds for a class of frequency assignment problems. IEEE Trans. Vehicular Tech. (1986) 35:8–14Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Company, San Francisco) Google Scholar
• Glover F., Laguna M.Tabu Search (1997) (Kluwer Academic Publishers, Norwell, MA) Crossref, Google Scholar
• Hertz A., de Werra D. Using tabu search techniques for graph coloring. Computing (1987) 39:345–351Crossref, Google Scholar
• Johnson D. S., Trick M. A.Cliques, Coloring, and Satisfiability: 2nd DIMACS Implementation Challange, 1993 (1996) (American Mathematical Society, Providence, RI) DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• Johnson D. S., Aragon C. R., McGeoch L. A., Schevon C. Optimization by simulated annealing: An experimental evaluation; Part II, graph coloring and number partitioning. Oper. Res. (1991) 39:378–406Link, Google Scholar
• Leighton F. T. A graph coloring algorithm for large scheduling problems. J. Res. National Bureau Standards (1979) 84:489–503Crossref, Google Scholar
• Mehrotra A., Trick M. A. A column generation approach for graph coloring. INFORMS J. Comput. (1996) 8:344–354Link, Google Scholar
• Monaci M., Toth P. A set-covering based heuristic approach for bin-packing problems. INFORMS J. Comput. (2006) 18:71–85Link, Google Scholar
• Morgenstern C. A., Johnson D. S., Trick M. A. Distributed coloration neighborhood search. Cliques, Coloring, and Satisfiability: 2nd DIMACS Implementation Challange, 1993 (1996) (American Mathematical Society, Providence, RI) 335–358DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• Sager T. J., Lin S. A pruning procedure for exact graph coloring. ORSA J. Comput. (1991) 3:226–230Link, Google Scholar
• Sewell E. C., Johnson D. S., Trick M. A. An improved algorithm for exact graph coloring. Cliques, Coloring, and Satisfiability: 2nd DIMACS Implementation Challange, 1993 (1996) (American Mathematical Society, Providence, RI) 359–373DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• Woo T. K., Su S. Y. W., Newman Wolfe R. Resource allocation in a dynamically partitionable bus network using a graph coloring algorithm. IEEE Trans. Comm. (2002) 39:1794–1801Crossref, Google Scholar