On NP-hardness of the clique partition -- independence number gap recognition and related problems
From MaRDI portal
Publication:2368935
DOI10.1016/j.disc.2006.01.004zbMath1091.05049WikidataQ56874375 ScholiaQ56874375MaRDI QIDQ2368935
Stanislav Busygin, Dimitrii V. Pasechnik
Publication date: 28 April 2006
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2006.01.004
05B15: Orthogonal arrays, Latin squares, Room squares
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of completing partial Latin squares
- The sandwich theorem
- Semidefinite programming in combinatorial optimization
- Approximation of the Stability Number of a Graph via Copositive Programming
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph