Covering and packing pumpkin models

Dimitris Chatzidimitriou 1 Jean-Florent Raymond 2, 3 Ignasi Sau 3 Dimitrios M. Thilikos 1, 3
1 Department of Mathematics [Athens]
2 Department of Mathematics, Computer Science and Mechanics [Warsaw]
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Let θr (the r-pumpkin) be the multi-graph containing two vertices and r parallel edges between them. We say that a graph is a a θr-model if it can be transformed into θr after a (possibly empty) sequence of contractions. We prove that there is a function g : N → N such that, for every two positive integers k and q, if G is a Kq-minor-free graph, then either G contains a set of k vertex-disjoint subgraphs (a θr-model-vertex-packing) each isomorphic to a θr-model or a set of g(r)·log q ·k vertices (a θr-model-vertex-cover) meeting all subgraphs of G that are isomorphic to a θr-model. Our results imply a O(log OP T)-approximation for the maximum (minimum) size of a θr-model packing (θr-model covering) of a graph G.
Type de document :
Communication dans un congrès
ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. 9th International colloquium on graph theory and combinatorics, 2014, 〈http://oc.inpg.fr/conf/icgt2014/〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083652
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 17 novembre 2014 - 16:26:20
Dernière modification le : jeudi 15 novembre 2018 - 19:49:19
Document(s) archivé(s) le : vendredi 14 avril 2017 - 13:45:16

Fichier

pumkil-for-ICGT-2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01083652, version 1

Collections

ALGCO | LIRMM | MIPS | TDS-MACS | UNIV-MONTPELLIER

Citation

Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. Covering and packing pumpkin models. ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. 9th International colloquium on graph theory and combinatorics, 2014, 〈http://oc.inpg.fr/conf/icgt2014/〉. 〈lirmm-01083652〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

268

Téléchargements de fichiers

230

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD