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

DOI10.1007/978-3-642-21311-3_11zbMATH Open1302.90256OpenAlexW196852542MaRDI QIDQ3003279FDOQ3003279

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

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

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)

Cited In (6)

• The Maximum k-Colorable Subgraph Problem and Related Problems
• 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
• Mathematical Programming Models and Exact Algorithms
• Packing, partitioning, and covering symresacks

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)