(Meta) kernelization
DOI10.1145/2973749zbMATH Open1425.68137OpenAlexW2563156040WikidataQ59567396 ScholiaQ59567396MaRDI QIDQ3177820FDOQ3177820
Authors: Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos, Hans L. Bodlaender 
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-01483628/file/0904.0727.pdf
Recommendations
treewidthmonadic second-order logicparameterized complexitykernelizationpreprocessingfinite integer indexembedded graphsprotrusions
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Logic in computer science (03B70)
Cited In (59)
- Search-space reduction via essential vertices
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- Snakes and Ladders: A Treewidth Story
- Turán’s Theorem Through Algorithmic Lens
- A constant-factor approximation for weighted bond cover
- Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
- Modification to Planarity is Fixed Parameter Tractable
- Compactors for parameterized counting problems
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- A Retrospective on (Meta) Kernelization
- Towards a polynomial kernel for directed feedback vertex set
- Towards a polynomial kernel for directed feedback vertex set
- First-Order Model-Checking in Random Graphs and Complex Networks
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Title not available (Why is that?)
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Meta-kernelization with structural parameters
- Approximation and kernelization for chordal vertex deletion
- Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
- Counting problems in parameterized complexity
- Data-compression for parametrized counting problems on sparse graphs
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Meta-kernelization using Well-structured Modulators
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- Reinterpreting the kernel
- A survey of parameterized algorithms and the complexity of edge modification
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Kernelizations for Parameterized Counting Problems
- Reducing CMSO model checking to highly connected graphs
- Meta-kernelization with structural parameters
- Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
- Maximum cut parameterized by crossing number
- Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
- Meta-kernelization using well-structured modulators
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Parameterized analysis and crossing minimization problems
- Lower bounds for protrusion replacement by counting equivalence classes
- Sparse obstructions for minor-covering parameters
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Explicit linear kernels for packing problems
- Lean Tree-Cut Decompositions: Obstructions and Algorithms
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Kernels for packing and covering problems
- Treelength of series-parallel graphs
- Bidimensionality and kernels
- Confluence in data reduction: bridging graph transformation and kernelization
- Confluence in data reduction: bridging graph transformation and kernelization
- Lossy Kernels for Hitting Subgraphs
- Editing to a planar graph of given degrees
- On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- Partial vertex cover on graphs of bounded degeneracy
- Polynomial kernels for hitting forbidden minors under structural parameterizations
This page was built for publication: (Meta) kernelization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177820)
