Testing branch-width

DOI10.1016/j.jctb.2006.06.006zbMath1138.05070OpenAlexW1993704152MaRDI QIDQ875941

Sang-il Oum, P. D. Seymour

Publication date: 16 April 2007

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.2006.06.006

zbMATH Keywords

connectivity functiontanglerank-widthbranch-widthcarving-widthsymmetric submodular function

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (14)

Intertwining Connectivities for Vertex-Minors and Pivot-Minors ⋮ First order convergence of matroids ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ Rank-width: algorithmic and structural results ⋮ Decomposition width of matroids ⋮ Tangle and Maximal Ideal ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ Partitions versus sets: a case of duality ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Computing with Tangles ⋮ Submodular partition functions ⋮ Finding Branch-Decompositions of Matroids, Hypergraphs, and More

Cites Work

• Unnamed Item
• Graph minors. X: Obstructions to tree-decomposition
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Constructive linear time algorithms for branchwidth
• A Parametrized Algorithm for Matroid Branch-Width
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Testing branch-width