Contraction obstructions for treewidth
From MaRDI portal
Publication:2275894
DOI10.1016/J.JCTB.2011.02.008zbMATH Open1223.05022DBLPjournals/jct/FominGT11OpenAlexW2032762881WikidataQ60488556 ScholiaQ60488556MaRDI QIDQ2275894FDOQ2275894
Authors: Fedor V. Fomin, Dimitrios M. Thilikos, Petr A. Golovach 
Publication date: 10 August 2011
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2011.02.008
Recommendations
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Graphs on surfaces
- Graph minors. V. Excluding a planar graph
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- (Meta) Kernelization
- Bidimensionality and kernels
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Title not available (Why is that?)
- Contraction Bidimensionality: The Accurate Picture
- Graph minors. XVI: Excluding a non-planar graph
- Approximation algorithms for domination search
- On graph contractions and induced minors
- Linearity of grid minors in treewidth with applications through bidimensionality
- Bidimensional Parameters and Local Treewidth
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- The Bidimensional Theory of Bounded-Genus Graphs
- A simpler proof of the excluded minor theorem for higher surfaces
- Embedding grids in surfaces
- Combinatorial Local Planarity and the Width of Graph Embeddings
Cited In (25)
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Coverability and sub-exponential parameterized algorithms in planar graphs
- A Retrospective on (Meta) Kernelization
- Contraction bidimensionality of geometric intersection graphs
- Grid induced minor theorem for graphs of small degree
- Graph minors and parameterized algorithm design
- Succinct monotone circuit certification: planarity and parameterized complexity
- Contraction-bidimensionality of geometric intersection graphs
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case
- On the tree-width of even-hole-free graphs
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Succinct certification of monotone circuits
- An algorithmic meta-theorem for graph modification to planarity and FOL
- Parameterizing cut sets in a graph by the number of their components
- Computing the best-case energy complexity of satisfying assignments in monotone circuits
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- To approximate treewidth, use treelength!
- Explicit linear kernels for packing problems
- The structure of obstructions to treewidth and pathwidth
- Large Induced Subgraphs via Triangulations and CMSO
- On the parameterized complexity of the edge monitoring problem
- Bidimensionality and kernels
- Title not available (Why is that?)
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)
