How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
DOI10.4230/LIPICS.IPEC.2017.10zbMATH Open1443.68071OpenAlexW2936634590MaRDI QIDQ5111869FDOQ5111869
Authors: Marin Bougeret, Ignasi Sau 
Publication date: 27 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8556/pdf/LIPIcs-IPEC-2017-10.pdf/
Recommendations
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Kernelization using structural parameters on sparse graph classes
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- Tight kernel bounds for problems on graphs with small degeneracy
- Polynomial kernels for vertex cover parameterized by small degree modulators
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- On problems without polynomial kernels
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Incompressibility through Colors and IDs
- (Meta) Kernelization
- Bidimensionality and kernels
- Infeasibility of instance compression and succinct PCPs for NP
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Sparsity. Graphs, structures, and algorithms
- Parameterized and Exact Computation
- Kernelization using structural parameters on sparse graph classes
- Reflections on multivariate algorithmics and problem parameterization
- On the hardness of losing width
- Crown structures for vertex cover kernelization
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Explicit linear kernels via dynamic programming
- Vertex cover structural parameterization revisited
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- A faster parameterized algorithm for treedepth
Cited In (7)
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Optimal data reduction for graph coloring using low-degree polynomials
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Kernelization using structural parameters on sparse graph classes
- Grid recognition: classical and parameterized computational perspectives
- Twin-width and polynomial kernels
This page was built for publication: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111869)
