Contraction obstructions for treewidth
From MaRDI portal
Recommendations
Cites work
- (Meta) Kernelization
- A simpler proof of the excluded minor theorem for higher surfaces
- Approximation algorithms for domination search
- Bidimensional Parameters and Local Treewidth
- Bidimensionality and kernels
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Contraction Bidimensionality: The Accurate Picture
- Embedding grids in surfaces
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XVI: Excluding a non-planar graph
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Graphs on surfaces
- Highly connected sets and the excluded grid theorem
- scientific article; zbMATH DE number 6783430 (Why is no real title available?)
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Linearity of grid minors in treewidth with applications through bidimensionality
- On graph contractions and induced minors
- Quickly excluding a planar graph
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- The Bidimensional Theory of Bounded-Genus Graphs
Cited in
(28)- The structure of obstructions to treewidth and pathwidth
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- Explicit linear kernels for packing problems
- On the tree-width of even-hole-free graphs
- Succinct monotone circuit certification: planarity and parameterized complexity
- Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case
- Succinct certification of monotone circuits
- Computing the best-case energy complexity of satisfying assignments in monotone circuits
- Grid induced minor theorem for graphs of small degree
- Graph minors and parameterized algorithm design
- Large Induced Subgraphs via Triangulations and CMSO
- The Structure and Number of Obstructions to Treewidth
- Bidimensionality and kernels
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- On supergraphs satisfying CMSO properties
- A Retrospective on (Meta) Kernelization
- On the parameterized complexity of the edge monitoring problem
- Contraction-bidimensionality of geometric intersection graphs
- To approximate treewidth, use treelength!
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- An algorithmic meta-theorem for graph modification to planarity and FOL
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- Parameterizing cut sets in a graph by the number of their components
- Sparse induced subgraphs of large treewidth
- An algorithmic meta-theorem for graph modification to planarity and FOL
- Contraction bidimensionality of geometric intersection graphs
This page was built for publication: Contraction obstructions for treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275894)
