How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
DOI10.4230/LIPICS.IPEC.2017.10zbMATH Open1443.68071OpenAlexW2936634590MaRDI QIDQ5111869FDOQ5111869
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 Geometric Graphs
- 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
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Reflections on Multivariate Algorithmics and Problem Parameterization
- On the hardness of losing width
- Crown structures for vertex cover kernelization
- Title not available (Why is that?)
- Explicit Linear Kernels via Dynamic Programming
- Vertex Cover Structural Parameterization Revisited
- Title not available (Why is that?)
- A Faster Parameterized Algorithm for Treedepth
Cited In (5)
- 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
- Grid recognition: classical and parameterized computational perspectives
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)
