Packing subgraphs in a graph - Manić, Gordana; Wakabayashi, Yoshiko (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2007: Anais do XX Concurso de Teses e Dissertações, 2007)
For a fixed family F of graphs, an F-packing of a graph G is a set of pairwise vertex-disjoint (or edge-disjoint) subgraphs of G, each isomorphic to an element of F. We focus on the algorithmic aspects of the problem of finding an F-packing that maximizes the number of covered edges. We present results for F = K 3 and F = {K 2 , K 3 }. For F = K 3 , we present approximation algorithms for bounded degree graphs, improving the ratio known for the general case. When F = {K 2 , K 3 }, we study the vertex-disjoint version. We prove that this problem is APX-hard even on graphs with maximum degree 4. Furthermore, we present a (3/2+ε)-approximation algorithm for arbitrary graphs, and a 1.4-approximation algorithm for graphs with maximum degree 4.