scientific article

DOI10.4230/LIPIcs.STACS.2011.189zbMath1230.68107arXiv1010.1365MaRDI QIDQ3113683

Neeldhara Misra, Fedor V. Fomin, Daniel Lokshtanov, Geevarghese Philip, Saket Saurabh

Publication date: 23 January 2012

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

graph minorskernelization\(p\)-\(\mathcal{F}\)-Deletion problemsprotrusion techniques

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (22)

Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths ⋮ Linear kernels for separating a graph into components of bounded size ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ On the Hardness of Losing Width ⋮ Uniform Kernelization Complexity of Hitting Forbidden Minors ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ Parameterized complexity of vertex deletion into perfect graph classes ⋮ Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ On the hardness of losing width ⋮ Confronting intractability via parameters ⋮ Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. ⋮ On parameterized independent feedback vertex set ⋮ Unnamed Item ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Parameterized Complexity of Vertex Deletion into Perfect Graph Classes ⋮ On sparsification for computing treewidth

This page was built for publication: