Branch-cut-and-propagate for the maximum k-colorable subgraph problem with symmetry

DOI10.1007/978-3-642-21311-3_11MaRDI QIDQ3003279zbMATH OpenOpenAlexFDO

Authors Tim Januschowski, Marc E. Pfetsch

Publication date 26 May 2011

Published in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21311-3_11

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Recommendations

• The maximum k-colorable subgraph problem and orbitopes
• A branch-and-cut algorithm for graph coloring
• A cutting plane algorithm for graph coloring
• scientific article; zbMATH DE number 2084276
• A polyhedral approach for graph coloring

Cited in

(7)

• The Maximum k-Colorable Subgraph Problem and Related Problems
• Mathematical programming models and exact algorithms
• Mixed-integer programming techniques for the connected max-\(k\)-cut problem
• A polyhedral investigation of star colorings
• The maximum k-colorable subgraph problem and orbitopes
• Symmetry breaking constraints for the minimum deficiency problem
• Packing, partitioning, and covering symresacks

Describes a project that uses

Uses Software

• SCIP

This page was built for publication: Branch-cut-and-propagate for the maximum \(k\)-colorable subgraph problem with symmetry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3003279)