The Structure and Number of Obstructions to Treewidth

DOI10.1137/S0895480195280010zbMath0869.05060MaRDI QIDQ3128210

Siddharthan Ramachandramurthi

Publication date: 20 August 1997

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

zbMATH Keywords

characterizationtreewidthgraph minorobstruction set

Mathematics Subject Classification ID

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

Related Items (12)

The structure of obstructions to treewidth and pathwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Differential geometric treewidth estimation in adiabatic quantum computation ⋮ Sparse obstructions for minor-covering parameters ⋮ Achievable sets, brambles, and sparse treewidth obstructions ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Treewidth lower bounds with brambles ⋮ Weighted Treewidth Algorithmic Techniques and Results ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Treewidth computations. II. Lower bounds ⋮ Minor obstructions for apex-pseudoforests

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