Uniform Kernelization Complexity of Hitting Forbidden Minors
From MaRDI portal
Publication:3448821
DOI10.1007/978-3-662-47672-7_51zbMath1441.68107arXiv1502.03965OpenAlexW2605868060MaRDI QIDQ3448821
Daniel Lokshtanov, Archontia C. Giannopoulou, Saket Saurabh, Bart M. P. Jansen
Publication date: 27 October 2015
Published in: ACM Transactions on Algorithms, Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.03965
Related Items
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies, Uniform Kernelization Complexity of Hitting Forbidden Minors, A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion, Sparse obstructions for minor-covering parameters, Quick but odd growth of cacti, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, Approximation and Kernelization for Chordal Vertex Deletion, Kernelization Algorithms for Packing Problems Allowing Overlaps, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, On the lossy kernelization for connected treedepth deletion set, Polynomial kernels for hitting forbidden minors under structural parameterizations, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations., On the Parameterized Complexity of Clique Elimination Distance, A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs, Hitting Forbidden Minors: Approximation and Kernelization, A polynomial kernel for distance-hereditary vertex deletion, A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs, Modification to Planarity is Fixed Parameter Tractable, Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps, Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Graph minors. I. Excluding a forest
- Graph minors. V. Excluding a planar graph
- Graph minors. XIII: The disjoint paths problem
- Tree-depth, subgraph coloring and homomorphism bounds
- Kernelization Using Structural Parameters on Sparse Graph Classes
- On the Hardness of Losing Width
- Kernel Bounds for Structural Parameterizations of Pathwidth
- Uniform Kernelization Complexity of Hitting Forbidden Minors
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- A Faster Parameterized Algorithm for Treedepth
- (Meta) Kernelization
- Polynomial bounds for the grid-minor theorem
- Bidimensionality and Geometric Graphs
