The maximum \(k\)-colorable subgraph problem and orbitopes
From MaRDI portal
Publication:666000
DOI10.1016/j.disopt.2011.04.002zbMath1233.90240OpenAlexW2086628398MaRDI QIDQ666000
Marc E. Pfetsch, Tim Januschowski
Publication date: 7 March 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2011.04.002
Integer programming (90C10) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)
Related Items
A polyhedral investigation of star colorings, Mathematical Programming Models and Exact Algorithms, Online algorithms for the maximum \(k\)-colorable subgraph problem, The Maximum k-Colorable Subgraph Problem and Related Problems, Lexicographical order in integer programming, Polytopes associated with symmetry handling, Packing, partitioning, and covering symresacks, A polyhedral approach for the equitable coloring problem, The maximum \(k\)-colorable subgraph problem and orbitopes, Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
Cites Work
- Unnamed Item
- Unnamed Item
- The maximum \(k\)-colorable subgraph problem and orbitopes
- Packing and partitioning orbitopes
- The node-deletion problem for hereditary properties is NP-complete
- Exact solution of bin-packing problems using column generation and branch-and-bound
- On perfectness of sums of graphs
- Geometric algorithms and combinatorial optimization.
- On certain polytopes associated with graphs
- Pruning by isomorphism in branch-and-cut
- Exploiting orbits in symmetric ILP
- On the \(k\)-coloring of intervals
- Polyhedral results for the bipartite induced subgraph problem
- Symmetric ILP: Coloring and small integers
- Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry
- Extended Formulations for Packing and Partitioning Orbitopes
- Constraint Orbital Branching
- Symmetry in Integer Linear Programming
- Fundamental Domains for Integer Programs with Symmetries
- Graph Bipartization and via minimization
- Facet of regular 0–1 polytopes
- A Column Generation Approach for Graph Coloring
- The approximation of maximum subgraph problems
- Orbitopal Fixing
