Approximation algorithms and hardness results for the clique packing problem

DOI10.1016/J.DAM.2008.10.017MaRDI QIDQ5902134zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsAPX-hardnesscliquepackingtriangle

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms and hardness results for the clique packing problem
• The \(K_r\)-packing problem
• An approximation algorithm for maximum triangle packing
• Packings by cliques and by finite families of graphs
• Constructive Packings of Triple Systems

Cites work

• Approximating k-set cover and complementary graph coloring
• Approximation algorithms and hardness results for the clique packing problem
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• 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
• Packing triangles in bounded degree graphs.
• Packing triangles in low degree graphs and indifference graphs
• Packings by cliques and by finite families of graphs

Cited in

(18)

• The complexity of generalized clique packing
• XSAT and NAE-SAT of linear CNF classes
• LP-based dual bounds for the maximum quasi-clique problem
• The three-dimensional stable roommates problem with additively separable preferences
• Approximation Algorithms for the k-Clique Covering Problem
• Approximation algorithms for maximum weight k-coverings of graphs by packings
• Inapproximability of \(H\)-transversal/packing
• Approximation algorithms and hardness results for the clique packing problem
• The \(K_r\)-packing problem
• On the parameterized complexity of compact set packing
• Approximating the directed path partition problem
• Packing K_rs in bounded degree graphs
• On cluster editing problem with clusters of small sizes
• On the parameterized complexity of compact set packing
• The maximum 3-star packing problem in claw-free cubic graphs
• Approximation algorithms for graph clustering problems with clusters of bounded size
• On linear and semidefinite programming relaxations for hypergraph matching
• Approximation algorithms for the cluster editing problem with small clusters

This page was built for publication: Approximation algorithms and hardness results for the clique packing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5902134)