Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/1079
Type: Artigo de periódico
Title: Approximation algorithms and hardness results for the clique packing problem
Author: CHATAIGNER, F.
MANIC, 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(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. (C) 2008 Elsevier B.V. All rights reserved.
Subject: Approximation algorithms
APX-hardness
Clique
Packing
Triangle
Country: Holanda
Editor: ELSEVIER SCIENCE BV
Rights: fechado
Identifier DOI: 10.1016/j.dam.2008.10.017
Address: http://apps.isiknowledge.com/InboundService.do?Func=Frame&product=WOS&action=retrieve&SrcApp=EndNote&UT=000264989500009&Init=Yes&SrcAuth=ResearchSoft&mode=FullRecord
http://dx.doi.org/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 
art_CHATAIGNER_Approximation_algorithms_and_hardness_results_for_the_2009.pdfpublished version1.03 MBAdobe PDFView/Open


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