The Maximum k-Colorable Subgraph Problem and Related Problems
From MaRDI portal
Publication:5084675
DOI10.1287/ijoc.2021.1086OpenAlexW3162383213MaRDI QIDQ5084675
Olga Kuryatnikova, Renata Sotirov, Juan Carlos Vera
Publication date: 28 June 2022
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2001.09644
semidefinite programmingstable setJohnson graphsHamming graphschromatic number of a graph\(k\)-colorable subgraph problemgeneralized theta number
Related Items (6)
Mathematical Programming Models and Exact Algorithms ⋮ On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs ⋮ Partitioning through projections: strong SDP bounds for large graph partition problems ⋮ On Integrality in Semidefinite Programming for Discrete Optimization ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving VLSI design and DNA sequencing problems using bipartization of graphs
- The maximum \(k\)-colorable subgraph problem and orbitopes
- The MIN-cut and vertex separator problem
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- The maximum k-colorable subgraph problem for chordal graphs
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- The node-deletion problem for hereditary properties is NP-complete
- Optimization, approximation, and complexity classes
- Geometric algorithms and combinatorial optimization
- Laplacian eigenvalues and the maximum cut problem
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Online algorithms for the maximum \(k\)-colorable subgraph problem
- Independence number of products of Kneser graphs
- Symmetry groups, semidefinite programs, and sums of squares
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- On the chromatic number, colorings, and codes of the Johnson graph
- Semidefinite programming relaxations for the graph partitioning problem
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Polyhedral results for the bipartite induced subgraph problem
- Constructive algorithms for the partial directed weighted improper coloring problem
- SDP Relaxations for Some Combinatorial Optimization Problems
- .879-approximation algorithms for MAX CUT and MAX 2SAT
- A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems
- An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
- Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry
- On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming
- A new table of constant weight codes
- Graphs with Given Group and Given Graph-Theoretical Properties
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- The Operator $\Psi$ for the Chromatic Number of a Graph
- A comparison of the Delsarte and Lovász bounds
- On the Shannon capacity of a graph
- The approximation of maximum subgraph problems
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Reducibility among Combinatorial Problems
- On spectrum sharing games
- Experimental and Efficient Algorithms
- Semidefinite relaxations for partitioning, assignment and ordering problems
This page was built for publication: The Maximum k-Colorable Subgraph Problem and Related Problems
