Covering and packing pumpkin models - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2014

Covering and packing pumpkin models

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.
Fichier principal
Vignette du fichier
pumkil-for-ICGT-2014.pdf (292.8 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01083652 , version 1 (17-11-2014)

Identifiers

  • HAL Id : lirmm-01083652 , version 1

Cite

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. ⟨lirmm-01083652⟩
252 View
169 Download

Share

More