On sparsification for computing treewidth
type: Item
instance of: scholarly article
title: On sparsification for computing treewidth
title: On Sparsification for Computing Treewidth
zbMATH Open document ID: 1312.68103
zbMATH Open document ID: 1309.68096
DOI: 10.1007/978-3-319-03898-8_19
DOI: 10.1007/S00453-014-9924-2
author: Bart M. P. Jansen
published in: Algorithmica
published in: Parameterized and Exact Computation
publication date: 2015-05-04T00:00:00Z
publication date: 2013-12-10T00:00:00Z
full work available at URL: https://arxiv.org/abs/1308.3665
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6432672
zbMATH DE Number: 6237070
zbMATH Keywords: sparsification
zbMATH Keywords: lower bounds
zbMATH Keywords: treewidth
zbMATH Keywords: kernelization
MaRDI profile type: Publication
OpenAlex ID: W2117427564
OpenAlex ID: W2478921387
arXiv ID: 1308.3665
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: On problems without polynomial kernels
cites work: On Exact Algorithms for Treewidth
cites work: Which problems have strongly exponential complexity?
cites work: Kernel Bounds for Structural Parameterizations of Pathwidth
cites work: Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Safe separators for treewidth
cites work: Nondeterminism within $P^ * $
cites work: Crown reductions for the minimum weighted vertex cover problem
cites work: The structure of obstructions to treewidth and pathwidth
cites work: Q3651735
cites work: Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
cites work: Q5743378
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: Safe reduction rules for weighted treewidth
cites work: FPT Is Characterized by Useful Obstruction Sets
cites work: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
cites work: Parametrized complexity theory.
cites work: Q3113683
cites work: The Marriage Problem
cites work: Q5743381
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Triangulating graphs without asteroidal triples
cites work: Achievable sets, brambles, and sparse treewidth obstructions
cites work: Min Cut is NP-complete for edge weighted trees
cites work: A 4 k 2 kernel for feedback vertex set
cites work: Some consequences of non-uniform conditions on uniform classes
Recommended article: On treewidth approximations
Recommended article: Graph-Theoretic Concepts in Computer Science
Recommended article: Better Approximations for Tree Sparsity in Nearly-Linear Time
Recommended article: Vertex Sparsification in Trees
Recommended article: On Exact Algorithms for Treewidth
Recommended article: Approximation algorithms for treewidth
Recommended article: On Tamaki's Algorithm to Compute Treewidths.
Recommended article: Q4699283
Recommended article: Q5150500
description: scientific article; zbMATH DE number 6237070
alternative label: On Sparsification for Computing Treewidth