Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry

DOI10.1007/978-3-642-21311-3_11zbMath1302.90256OpenAlexW196852542MaRDI QIDQ3003279

Marc E. Pfetsch, Tim Januschowski

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

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

Related Items (6)

A polyhedral investigation of star colorings ⋮ Mathematical Programming Models and Exact Algorithms ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Packing, partitioning, and covering symresacks ⋮ The maximum \(k\)-colorable subgraph problem and orbitopes ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem

Uses Software

• SCIP

This page was built for publication: Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry