The Structure and Number of Obstructions to Treewidth

DOI10.1137/S0895480195280010MaRDI QIDQ3128210zbMATH OpenFDO

Authors Siddharthan Ramachandramurthi

Publication date 20 August 1997

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480195280010

zbMATH Keywords

characterizationgraph minorobstruction settreewidth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The structure of obstructions to treewidth and pathwidth
• scientific article; zbMATH DE number 475617
• Achievable sets, brambles, and sparse treewidth obstructions
• Contraction obstructions for treewidth

Cited in

(18)

• The structure of obstructions to treewidth and pathwidth
• A branch-and-price-and-cut method for computing an optimal bramble
• Minor obstructions for apex-pseudoforests
• Sparse obstructions for minor-covering parameters
• Contraction obstructions for treewidth
• Obstructions for tree-depth
• Graph minors and parameterized algorithm design
• Differential geometric treewidth estimation in adiabatic quantum computation
• Characterizing width two for variants of treewidth
• scientific article; zbMATH DE number 475617 (Why is no real title available?)
• On making a distinguished vertex of minimum degree by vertex deletion
• Weighted Treewidth Algorithmic Techniques and Results
• Treewidth computations. II. Lower bounds
• k-apices of minor-closed graph classes. I: Bounding the obstructions
• A lower bound for treewidth and its consequences
• Graph parameters, universal obstructions, and WQO
• Achievable sets, brambles, and sparse treewidth obstructions
• Treewidth lower bounds with brambles

This page was built for publication: The Structure and Number of Obstructions to Treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3128210)