A Branch-and-Cut Algorithm for Equitable Coloring based on a Formulation by Representatives

DOI10.1016/j.endm.2009.11.057zbMath1268.90110OpenAlexW2114903113MaRDI QIDQ2840561

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

Publication date: 19 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.11.057

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems, A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph, A polyhedral approach for the equitable coloring problem, Integer programming formulations and efficient local search for relaxed correlation clustering, Polyhedral results for the Equitable Coloring Problem

Cites Work

• Unnamed Item
• Cliques, holes and the vertex coloring polytope
• A branch-and-cut algorithm for partition coloring
• Equitable Coloring
• Perfect Graphs and an Application to Optimizing Municipal Services