Approximation algorithms and hardness results for the clique packing problem

DOI10.1016/j.dam.2008.10.017zbMath1172.05046OpenAlexW2049206926MaRDI QIDQ5902134

Frédéric Chataigner, Yoshiko Wakabayashi, Raphael Yuster, Gordana Manić

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.10.017

zbMATH Keywords

trianglepackingcliqueapproximation algorithmsAPX-hardness

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

LP-based dual bounds for the maximum quasi-clique problem, The three-dimensional stable roommates problem with additively separable preferences, Inapproximability of $H$-Transversal/Packing, On the parameterized complexity of compact set packing, Approximating the directed path partition problem, XSAT and NAE-SAT of linear CNF classes, On linear and semidefinite programming relaxations for hypergraph matching

Cites Work

• Unnamed Item
• Packings by cliques and by finite families of graphs
• Packing triangles in bounded degree graphs.
• Packing triangles in low degree graphs and indifference graphs
• On the Complexity of General Graph Factor Problems
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Approximating k-set cover and complementary graph coloring
• Approximation algorithms and hardness results for the clique packing problem