How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
type: Item
instance of: scholarly article
zbMATH Open document ID: 1443.68071
author: Marin Bougeret
author: Ignasi Sau
publication date: 2020-05-27T00:00:00Z
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7205194
zbMATH Keywords: parameterized complexity
zbMATH Keywords: polynomial kernels
zbMATH Keywords: structural parameters
zbMATH Keywords: treedepth
zbMATH Keywords: treewidth
zbMATH Keywords: sparse graphs
MaRDI profile type: Publication
cites work: Crown structures for vertex cover kernelization
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: On the hardness of losing width
cites work: Incompressibility through Colors and IDs
cites work: Bidimensionality and Geometric Graphs
cites work: Vertex Cover Structural Parameterization Revisited
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Kernelization using structural parameters on sparse graph classes
cites work: Explicit Linear Kernels via Dynamic Programming
cites work: Parameterized and Exact Computation
cites work: Q3113682
cites work: Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
cites work: Q5363786
cites work: Sparsity. Graphs, structures, and algorithms
cites work: Reflections on Multivariate Algorithmics and Problem Parameterization
cites work: Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
cites work: A Faster Parameterized Algorithm for Treedepth
full work available at URL: LIPIcs-IPEC-2017-10.pdf
OpenAlex ID: W2936634590
title: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
DOI: 10.4230/LIPICS.IPEC.2017.10
description: scientific article; zbMATH DE number 7205194