Please use this identifier to cite or link to this item:
Type: Artigo
Title: Approximation algorithms and hardness results for the clique packing problem
Author: Chataigner, F.
Manić, G.
Wakabayashi, Y.
Yuster, R.
Abstract: For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K-2}. In this paper we provide new approximation algorithms and hardness results for the K-r-packing problem where K-r = {K-2, K-3,K- . . . , K-r}. We show that already for r = 3 the K-r-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation
Subject: Algoritmos de aproximação
Country: Países Baixos
Editor: Elsevier
Rights: Fechado
Identifier DOI: 10.1016/j.dam.2008.10.017
Date Issue: 2009
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
000264989500009.pdf1.1 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.