Packing triangles in low degree graphs and indifference graphs

Abstract : We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation guarantee known so far for these problems has ratio $3/2 + ɛ$, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver in 1989. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs.
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.251-256, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184365
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:37:39
Dernière modification le : dimanche 17 décembre 2017 - 06:54:05
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:01:34

Fichier

dmAE0150.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184365, version 1

Collections

Citation

Gordana Manić, Yoshiko Wakabayashi. Packing triangles in low degree graphs and indifference graphs. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.251-256, 2005, DMTCS Proceedings. 〈hal-01184365〉

Partager

Métriques

Consultations de la notice

257

Téléchargements de fichiers

191