Meta-kernelization with structural parameters
DOI10.1016/J.JCSS.2015.08.003zbMATH Open1346.68109OpenAlexW1903283433WikidataQ124813044 ScholiaQ124813044MaRDI QIDQ896025FDOQ896025
Authors: Robert Ganian, Friedrich Slivovsky, Stefan Szeider 
Publication date: 11 December 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2015.08.003
Recommendations
modular decompositionclique-widthmonadic second-order logicparameterized complexitykernelizationrank-widthBoolean width
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Decidability of theories and sets of sentences (03B25)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Kernels: Annotated, Proper and Induced
- On problems without polynomial kernels
- Algorithmic meta-theorems for restrictions of treewidth
- Linear time solvable optimization problems on graphs of bounded clique-width
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Kernelization -- preprocessing with a guarantee
- Graph structure and monadic second-order logic. A language-theoretic approach
- Easy problems for tree-decomposable graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Elements of finite model theory.
- Title not available (Why is that?)
- (Meta) Kernelization
- Infeasibility of instance compression and succinct PCPs for NP
- Kernelization using structural parameters on sparse graph classes
- Linear time split decomposition revisited
- Decomposition of Directed Graphs
- Boolean-width of graphs
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Partitive hypergraphs
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Finding Branch-Decompositions and Rank-Decompositions
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Algorithmic aspects of a general modular decomposition theory
- Lower bounds on kernelization
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- Meta-kernelization using Well-structured Modulators
- Title not available (Why is that?)
Cited In (13)
- A Retrospective on (Meta) Kernelization
- Meta-kernelization with structural parameters
- Data-compression for parametrized counting problems on sparse graphs
- Meta-kernelization using Well-structured Modulators
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Kernelization using structural parameters on sparse graph classes
- On structural parameterizations of the bounded-degree vertex deletion problem
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Solving problems on graphs of high rank-width
- (Meta) kernelization
- Meta-kernelization using well-structured modulators
- On structural parameterizations of the bounded-degree vertex deletion problem
- Solving problems on graphs of high rank-width
This page was built for publication: Meta-kernelization with structural parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896025)
