A Wide Branching Strategy for the Graph Coloring Problem

DOI10.1287/ijoc.2014.0593zbMath1304.90211MaRDI QIDQ2940061

Edward C. Sewell, David R. Morrison, Jason J. Sauppe, Jacobson, Sheldon H.

Publication date: 26 January 2015

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/0b96ff3f895b754a5d9b7c17d2458e64db4b90dc

zbMATH Keywords

integer programming; computational experiments; graph coloring; branch-and-price

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C10: Integer programming

90C27: Combinatorial optimization

05C15: Coloring of graphs and hypergraphs

Related Items

Lower bounding techniques for DSATUR-based branch and bound, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• An exact approach for the vertex coloring problem
• Branching in branch-and-price: A generic scheme
• Simple ingredients leading to very efficient heuristics for the maximum clique problem
• The vertex coloring problem and its generalizations
• A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
• Maximum-weight stable sets and safe lower bounds for graph coloring
• A survey of local search methods for graph coloring
• A branch-and-cut algorithm for graph coloring
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
• A Branch-and-Price Algorithm for the Bin Packing Problem with Conflicts
• A Metaheuristic Approach for the Vertex Coloring Problem
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A survey on vertex coloring problems
• A Column Generation Approach for Graph Coloring
• A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems
• Investigation of some branch and bound strategies for the solution of mixed integer linear programs