Approximate Turing Kernelization for Problems Parameterized by Treewidth
From MaRDI portal
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
- (Meta) kernelization
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- A completeness theory for polynomial (Turing) kernelization
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- A hierarchy of polynomial kernels
- A Polynomial Kernel for Diamond-Free Editing
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- An approximate kernel for connected feedback vertex set
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Clique Cover and Graph Separation
- Connected Treewidth and Connected Graph Searching
- Depth-first search and the vertex cover problem
- scientific article; zbMATH DE number 1420918 (Why is no real title available?)
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Infeasibility of instance compression and succinct PCPs for NP
- Interval vertex deletion admits a polynomial kernel
- Kernel bounds for disjoint cycles and disjoint paths
- Kernel(s) for problems with no kernel
- Kernelization lower bounds through colors and IDs
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Kernelization. Theory of parameterized preprocessing
- Kernels for edge dominating set: simpler or smaller
- Lossy kernelization
- Lossy kernels for connected dominating set on sparse graphs
- Lossy Kernels for Hitting Subgraphs
- On kernelization for edge dominating set under structural parameters
- On problems without polynomial kernels
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
Cited in
(2)
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)
