A Wide Branching Strategy for the Graph Coloring Problem

DOI10.1287/ijoc.2014.0593zbMath1304.90211OpenAlexW2145765528MaRDI 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 programmingcomputational experimentsgraph coloringbranch-and-price

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

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

This page was built for publication: A Wide Branching Strategy for the Graph Coloring Problem