Branch decompositions and minor containment

DOI10.1002/net.10099zbMath1031.05121OpenAlexW1998477972MaRDI QIDQ4446913

Illya V. Hicks

Publication date: 3 February 2004

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.10099

zbMATH Keywords

dynamic programminggraph minorobstruction setbranchwidthbranch decompositionminor containment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Tree-width and the Sherali-Adams operator, Irrelevant vertices for the planar disjoint paths problem, Tangle bases: Revisited, A Branch Decomposition Algorithm for the p-Median Problem, Minor embedding in broken chimera and derived graphs is NP-complete, A combinatorial optimization algorithm for solving the branchwidth problem, Square roots of minor closed graph classes, Faster parameterized algorithms for minor containment, Fast minor testing in planar graphs, Unnamed Item

Uses Software

• DIMACS

Cites Work

• Graph minors. I. Excluding a forest
• Constructive linear time algorithms for branchwidth
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item