Computing with Tangles

DOI10.1137/15M1027565zbMath1345.05101OpenAlexW2415388303MaRDI QIDQ5890774

Pascal Schweitzer, Martin Grohe

Publication date: 23 June 2016

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

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

zbMATH Keywords

tree decompositionconnectivity functiontangle

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Data structures (68P05) Connectivity (05C40)

Related Items

Canonisation and Definability for Graphs of Bounded Rank Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Connectivity and tree structure in finite graphs
• The structure of the models of decidable monadic theories of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Testing branch-width
• Tangles, tree-decompositions and grids in matroids
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XVI: Excluding a non-planar graph
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Certifying large branch-width
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
• A simpler algorithm and shorter proof for the graph minor decomposition
• A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
• Finding Branch-Decompositions and Rank-Decompositions