Meta-kernelization with structural parameters
From MaRDI portal
Publication:896025
Boolean widthclique-widthkernelizationmodular decompositionmonadic second-order logicparameterized complexityrank-width
Decidability of theories and sets of sentences (03B25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)
Recommendations
Cites work
- (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
- 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?)
- 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
(17)- Solving problems on graphs of high rank-width
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- On structural parameterizations of the bounded-degree vertex deletion problem
- 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
- Meta-kernelization with structural parameters
- (Meta) kernelization
- On structural parameterizations of the bounded-degree vertex deletion problem
- Solving problems on graphs of high rank-width
- A Retrospective on (Meta) Kernelization
- Data-compression for parametrized counting problems on sparse graphs
- Meta-kernelization using Well-structured Modulators
- Preprocessing complexity for some graph problems parameterized by structural parameters
- Fine-grained meta-theorems for vertex integrity
- Boundaried kernelization
- First order logic on pathwidth revisited again
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)
