Contraction obstructions for treewidth

DOI10.1016/j.jctb.2011.02.008zbMath1223.05022OpenAlexW2032762881WikidataQ60488556 ScholiaQ60488556MaRDI QIDQ2275894

Dimitrios M. Thilikos, Fedor V. Fomin, 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

zbMATH Keywords

treewidthgraph minorbidimensionalitygraph contraction

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (26)

A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case ⋮ Unnamed Item ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Computing the best-case energy complexity of satisfying assignments in monotone circuits ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Unnamed Item ⋮ Grid induced minor theorem for graphs of small degree ⋮ Parameterizing cut sets in a graph by the number of their components ⋮ Unnamed Item ⋮ Succinct certification of monotone circuits ⋮ On the tree-width of even-hole-free graphs ⋮ Explicit linear kernels for packing problems ⋮ On the parameterized complexity of the edge monitoring problem ⋮ To Approximate Treewidth, Use Treelength! ⋮ Succinct monotone circuit certification: planarity and parameterized complexity ⋮ The Parameterized Complexity of Graph Cyclability ⋮ Bidimensionality and Kernels ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Unnamed Item ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

Cites Work

• On graph contractions and induced minors
• Linearity of grid minors in treewidth with applications through bidimensionality
• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• Highly connected sets and the excluded grid theorem
• Quickly excluding a planar graph
• A simpler proof of the excluded minor theorem for higher surfaces
• Graph minors. XVI: Excluding a non-planar graph
• Embedding grids in surfaces
• Approximation Algorithms for Domination Search
• The Bidimensional Theory of Bounded-Genus Graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Contraction Bidimensionality: The Accurate Picture
• Combinatorial Local Planarity and the Width of Graph Embeddings
• (Meta) Kernelization
• Bidimensional Parameters and Local Treewidth
• Bidimensionality and Geometric Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Contraction obstructions for treewidth