Testing branch-width

DOI10.1016/J.JCTB.2006.06.006MaRDI QIDQ875941zbMATH OpenOpenAlexFDO

Authors Sang-Il Oum, Paul 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

tanglerank-widthbranch-widthconnectivity functioncarving-widthsymmetric submodular function

Mathematics Subject Classification ID

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

Recommendations

• Approximating clique-width and branch-width
• scientific article; zbMATH DE number 1304318
• Bounding branch-width
• A Parametrized Algorithm for Matroid Branch-Width
• Constructive linear time algorithms for branchwidth

Cites work

• scientific article; zbMATH DE number 2080246 (Why is no real title available?)
• A Parametrized Algorithm for Matroid Branch-Width
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Constructive linear time algorithms for branchwidth
• Graph minors. X: Obstructions to tree-decomposition
• Graph-Theoretic Concepts in Computer Science

Cited in

(17)

• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Tangle and Maximal Ideal
• Partitions versus sets: a case of duality
• Submodular partition functions
• Decomposition width of matroids
• Fast FPT-approximation of branchwidth
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Computing with tangles
• Testing Bandwidth k for k-Connected Graphs
• Intertwining Connectivities for Vertex-Minors and Pivot-Minors
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• First order convergence of matroids
• Bounding branch-width
• Finding branch-decompositions of matroids, hypergraphs, and more
• Rank-width: algorithmic and structural results
• Covering Vectors by Spaces: Regular Matroids
• scientific article; zbMATH DE number 1304318 (Why is no real title available?)

This page was built for publication: Testing branch-width

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