A Wide Branching Strategy for the Graph Coloring Problem

References

• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Brélaz D (1979) New methods to color the vertices of a graph. Comm. ACM 22(4):251–256.Crossref, Google Scholar
• Elhedhli S, Li L, Gzara M, Naoum-Sawaya J (2011) A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS J. Comput. 23(3):404–415.Link, Google Scholar
• Farley AA (1990) A note on bounding a class of linear programming problems, including cutting stock problems. Oper. Res. 38(5):922–923.Link, Google Scholar
• Galinier P, Hertz A (2006) A survey of local search methods for graph coloring. Comput. Oper. Res. 33(9):2547–2562.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st ed. (W. H. Freeman & Co., New York).Google Scholar
• Grosso A, Locatelli M, Pullan W (2008) Simple ingredients leading to very efficient heuristics for the maximum clique problem. J. Heuristics 14(6):587–612.Crossref, Google Scholar
• Gualandi S, Malucelli F (2012) Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24(1):81–100.Link, Google Scholar
• Held S, Cook W, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• Johnson DS, Trick MA (1996) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Lodi A, Ralphs TK, Rossi F, Smriglio S (2011) Interdiction branching. Technical report, COR@L Laboratory, Lehigh University, Bethlehem, PA.Google Scholar
• Malaguti E (2008) The vertex coloring problem and its generalizations. 4OR 7(1):101–104.Crossref, Google Scholar
• Malaguti E, Toth P (2010) A survey on vertex coloring problems. Internat. Trans. Oper. Res. 17(1):1–34.Crossref, Google Scholar
• Malaguti E, Monaci M, Toth P (2008) A metaheuristic approach for the vertex coloring problem. INFORMS J. Comput. 20(2):302–316.Link, Google Scholar
• Malaguti E, Monaci M, Toth P (2011) An exact approach for the vertex coloring problem. Discrete Optim. 8(2):174–190.Crossref, Google Scholar
• Mehrotra A, Trick MA (1996) A column generation approach for graph coloring. INFORMS J. Comput. 8(4):344–354.Link, Google Scholar
• Méndez-Díaz I, Zabala P (2006) A branch-and-cut algorithm for graph coloring. Discrete Appl. Math. 154(5):826–847.Crossref, Google Scholar
• Mitra G (1973) Investigation of some branch and bound strategies for the solution of mixed integer linear programs. Math. Programming 4(1):155–170.Crossref, Google Scholar
• Pardalos P, Mavridou T, Xue J (1999) The graph coloring problem: A bibliographic survey. Du D, Pardalos PM, eds. Handbook of Combinatorial Optimization (Springer, New York), 1077–1141.Google Scholar
• Sewell E (1996) An improved algorithm for exact graph coloring. Johnson DS, Trick MA, eds. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Vol. 26 (American Mathematical Society, Providence, RI), 359–372.Crossref, Google Scholar
• Sewell EC, Sauppe JJ, Morrison DR, Jacobson SH, Kao G (2012) A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times. J. Global Optim. 54(4):791–812.Crossref, Google Scholar
• Trick MA (2005) Computational series: Graph coloring and its generalizations. Accessed April 2014, http://mat.gsia.cmu.edu/COLOR02/.Google Scholar
• Vanderbeck F (2011) Branching in branch-and-price: A generic scheme. Math. Programming 130(2):249–294.Crossref, Google Scholar
• Zuckerman D (2006) Linear degree extractors and the inapproximability of max clique and chromatic number. Proc. Thirty-Eighth Annual ACM Sympos. Theory Comput. (STOC'06) (ACM, New York), 681–690.Crossref, Google Scholar