Approximate Turing Kernelization for Problems Parameterized by Treewidth
From MaRDI portal
Publication:5874531
DOI10.4230/LIPICS.ESA.2020.60OpenAlexW3082372257MaRDI QIDQ5874531FDOQ5874531
Authors: Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse 
Publication date: 7 February 2023
Full work available at URL: https://arxiv.org/abs/2004.12683
Recommendations
- On treewidth approximations
- Treewidth and the Computational Complexity of MAP Approximations
- Approximation algorithms for treewidth
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Inapproximability of treewidth and related problems
- Complexity lower bounds for approximation algebraic computation trees
- A \(c^k n\) 5-approximation algorithm for treewidth
- On Exact Algorithms for Treewidth
- FPT and kernelization algorithms for the induced tree problem
Cites Work
- On problems without polynomial kernels
- Depth-first search and the vertex cover problem
- Connected Treewidth and Connected Graph Searching
- Kernelization lower bounds through colors and IDs
- Infeasibility of instance compression and succinct PCPs for NP
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Clique Cover and Graph Separation
- Kernel bounds for disjoint cycles and disjoint paths
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Kernel(s) for problems with no kernel
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Kernels for edge dominating set: simpler or smaller
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- A completeness theory for polynomial (Turing) kernelization
- (Meta) kernelization
- Kernelization. Theory of parameterized preprocessing
- Lossy kernelization
- Title not available (Why is that?)
- Title not available (Why is that?)
- On kernelization for edge dominating set under structural parameters
- Interval vertex deletion admits a polynomial kernel
- A Polynomial Kernel for Diamond-Free Editing
- Lossy kernels for connected dominating set on sparse graphs
- A hierarchy of polynomial kernels
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- Lossy Kernels for Hitting Subgraphs
Cited In (1)
This page was built for publication: Approximate Turing Kernelization for Problems Parameterized by Treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874531)
