Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Approximation algorithms and hardness results for the clique packing problem

Texto completo
Autor(es):
Chataigner, F. [1] ; Manic, G. [2] ; Wakabayashi, Y. [1] ; Yuster, R. [3]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508 Sao Paulo - Brazil
[2] Univ Estadual Campinas, Inst Computacao, BR-13081970 Campinas, SP - Brazil
[3] Univ Haifa, Dept Math, IL-31999 Haifa - Israel
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: DISCRETE APPLIED MATHEMATICS; v. 157, n. 7, p. 1396-1406, APR 6 2009.
Citações Web of Science: 4
Resumo

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. (AU)

Processo FAPESP: 06/01817-7 - Modelagem matemática e aplicações de problemas de otimização relativos à busca de subgrafos com estruturas comuns
Beneficiário:Gordana Manic
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 05/53840-0 - Algoritimos de aproximacao, complexidade e nao-aproximabilidade de problemas em grafos.
Beneficiário:Frederic Chataigner
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
Beneficiário:Yoshiharu Kohayakawa
Linha de fomento: Auxílio à Pesquisa - Programa PRONEX - Temático