A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives

DOI10.1016/j.dam.2011.10.008zbMath1321.05251MaRDI QIDQ496694

Yuri Frota, Thiago F. Noronha, Laura Bahiense, Celso Carneiro Ribeiro

Publication date: 22 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.008

zbMATH Keywords

branch-and-cut; equitable coloring; tabu search heuristic

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

MIP formulations for induced graph optimization problems: a tutorial, The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study, A DSATUR-based algorithm for the equitable coloring problem, Solving vertex coloring problems as maximum weight stable set problems, \((N, p)\)-equitable \(b\)-coloring of graphs, Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope, Improving lower bounds for equitable chromatic number, A polyhedral approach for the equitable coloring problem, Iterated local search with tabu search for the weighted vertex coloring problem, A Tabu Search Heuristic for the Equitable Coloring Problem

Uses Software

• GRASP
• DIMACS

Cites Work

• Conflict-free star-access in parallel memory systems
• Cliques, holes and the vertex coloring polytope
• Equitable coloring of trees
• An Ore-type theorem on equitable coloring
• A branch-and-cut algorithm for partition coloring
• An annotated bibliography of GRASP-Part II: Applications
• An annotated bibliography of GRASP – Part I: Algorithms
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• Equitable Coloring
• A list analogue of equitable coloring
• Graph Colorings
• Perfect Graphs and an Application to Optimizing Municipal Services
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item