Meta-kernelization with structural parameters
From MaRDI portal
Publication:896025
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 6691415 (Why is no real title available?)
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- scientific article; zbMATH DE number 3799016 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- (Meta) Kernelization
- Algorithmic aspects of a general modular decomposition theory
- Algorithmic meta-theorems for restrictions of treewidth
- Approximating clique-width and branch-width
- Boolean-width of graphs
- Decomposition of Directed Graphs
- Easy problems for tree-decomposable graphs
- Elements of finite model theory.
- Finding Branch-Decompositions and Rank-Decompositions
- Graph minors. X: Obstructions to tree-decomposition
- Graph structure and monadic second-order logic. A language-theoretic approach
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- Infeasibility of instance compression and succinct PCPs for NP
- Kernelization -- preprocessing with a guarantee
- Kernelization using structural parameters on sparse graph classes
- Kernels: Annotated, Proper and Induced
- Linear time solvable optimization problems on graphs of bounded clique-width
- Linear time split decomposition revisited
- Lower bounds on kernelization
- Meta-kernelization using Well-structured Modulators
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- On problems without polynomial kernels
- Parametrized complexity theory.
- Partitive hypergraphs
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
Cited in
(13)- A Retrospective on (Meta) Kernelization
- Meta-kernelization with structural parameters
- Data-compression for parametrized counting problems on sparse graphs
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Meta-kernelization using Well-structured Modulators
- 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)
