Hitting and Harvesting Pumpkins

DOI10.1137/120883736zbMath1305.05221arXiv1105.2704OpenAlexW3100974949MaRDI QIDQ5892008

Ignasi Sau, Christophe Paul, Saket Saurabh, Gwenaël Joret, Steéphan Thomassé

Publication date: 22 December 2014

Published in: SIAM Journal on Discrete Mathematics, Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1105.2704

zbMATH Keywords

approximation algorithmparameterized complexitygraph minorsiterative compressionsingle-exponential algorithmhitting and packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (8)

An edge variant of the Erdős-Pósa property ⋮ Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ Quick but odd growth of cacti ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ Unavoidable minors for graphs with large \(\ell_p\)-dimension ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size

This page was built for publication: Hitting and Harvesting Pumpkins