Contraction obstructions for treewidth

DOI10.1016/J.JCTB.2011.02.008MaRDI QIDQ2275894zbMATH OpenOpenAlexDBLPWikidataFDO

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

zbMATH Keywords

treewidthgraph minorbidimensionalitygraph contraction

Mathematics Subject Classification ID

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

Recommendations

• The structure of obstructions to treewidth and pathwidth
• The Structure and Number of Obstructions to Treewidth
• Contraction and Treewidth Lower Bounds
• Contraction Bidimensionality: The Accurate Picture
• Graph contraction pattern matching for graphs of bounded treewidth

Cites work

• scientific article; zbMATH DE number 6783430 (Why is no real title available?)
• (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
• 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

(25)

• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• scientific article; zbMATH DE number 7471674 (Why is no real title available?)
• Coverability and sub-exponential parameterized algorithms in planar graphs
• Contraction bidimensionality of geometric intersection graphs
• A Retrospective on (Meta) Kernelization
• 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
• Parameterizing cut sets in a graph by the number of their components
• An algorithmic meta-theorem for graph modification to planarity and FOL
• 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

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)