On sparsification for computing treewidth
From MaRDI portal
Publication:2343087
DOI10.1007/s00453-014-9924-2zbMath1312.68103arXiv1308.3665OpenAlexW2117427564MaRDI QIDQ2343087
Publication date: 4 May 2015
Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1308.3665
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
Treewidth and pathwidth parameterized by the vertex cover number ⋮ Sparsification upper and lower bounds for graph problems and not-all-equal SAT ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ FPT is characterized by useful obstruction sets ⋮ Best-case and worst-case sparsifiability of Boolean CSPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some consequences of non-uniform conditions on uniform classes
- Safe separators for treewidth
- Safe reduction rules for weighted treewidth
- Achievable sets, brambles, and sparse treewidth obstructions
- On problems without polynomial kernels
- Min Cut is NP-complete for edge weighted trees
- A partial k-arboretum of graphs with bounded treewidth
- Which problems have strongly exponential complexity?
- The structure of obstructions to treewidth and pathwidth
- Triangulating graphs without asteroidal triples
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Crown reductions for the minimum weighted vertex cover problem
- Parametrized complexity theory.
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- FPT Is Characterized by Useful Obstruction Sets
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Kernel Bounds for Structural Parameterizations of Pathwidth
- Complexity of Finding Embeddings in a k-Tree
- Nondeterminism within $P^ * $
- Kernelization Lower Bounds by Cross-Composition
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- On Exact Algorithms for Treewidth
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- The Marriage Problem
This page was built for publication: On sparsification for computing treewidth
