Meta-kernelization with structural parameters
type: Item
instance of: scholarly article
title: Meta-kernelization with structural parameters
zbMATH Open document ID: 1346.68109
author: Robert Ganian
author: Friedrich Slivovsky
author: Stefan Szeider
published in: Journal of Computer and System Sciences
publication date: 2015-12-11T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 6520021
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization
zbMATH Keywords: rank-width
zbMATH Keywords: clique-width
zbMATH Keywords: Boolean width
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: modular decomposition
MaRDI profile type: Publication
full work available at URL: j.jcss.2015.08.003
OpenAlex ID: W1903283433
Wikidata QID: Q124813044
cites work: Kernels: Annotated, Proper and Induced
cites work: Easy problems for tree-decomposable graphs
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
cites work: Algorithmic aspects of a general modular decomposition theory
cites work: Boolean-width of graphs
cites work: Linear time split decomposition revisited
cites work: Partitive hypergraphs
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q3077955
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Decomposition of Directed Graphs
cites work: Q4947393
cites work: Q4263467
cites work: Meta-kernelization using Well-structured Modulators
cites work: The Lost Continent of Polynomial Time: Preprocessing and Kernelization
cites work: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
cites work: Parametrized complexity theory.
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Kernelization Using Structural Parameters on Sparse Graph Classes
cites work: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
cites work: Guarantees and limits of preprocessing in constraint satisfaction and reasoning
cites work: Q2965497
cites work: Finding Branch-Decompositions and Rank-Decompositions
cites work: Algorithmic meta-theorems for restrictions of treewidth
cites work: Elements of finite model theory.
cites work: Kernelization – Preprocessing with a Guarantee
cites work: Lower bounds on kernelization
cites work: Approximating clique-width and branch-width
cites work: Q4743737
cites work: Graph minors. X: Obstructions to tree-decomposition
DOI: 10.1016/J.JCSS.2015.08.003
description: scientific article; zbMATH DE number 6520021