 |
HAL-LIRMM - Open Archive |  |
Conference papers
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.
Cited literature [15 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083652
Contributor : Dimitrios Thilikos <>
Submitted on : Monday, November 17, 2014 - 4:26:20 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Friday, April 14, 2017 - 1:45:16 PM
Contributor : Dimitrios Thilikos <>
Submitted on : Monday, November 17, 2014 - 4:26:20 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Friday, April 14, 2017 - 1:45:16 PM
File
pumkil-for-ICGT-2014.pdf
Files produced by the author(s)