Computing with tangles

DOI10.1137/15M1027565MaRDI QIDQ5890774zbMATH OpenOpenAlexFDO

Authors Martin Grohe, P. Schweitzer

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

connectivity functiontangletree decomposition

Mathematics Subject Classification ID

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

Recommendations

• Computing with Tangles
• Tangles and connectivity in graphs
• Tangles, trees, and flowers
• Tangles, tree-decompositions and grids in matroids
• Refining a tree-decomposition which distinguishes tangles

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
• A simpler algorithm and shorter proof for the graph minor decomposition
• Approximating clique-width and branch-width
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Certifying large branch-width
• Connectivity and tree structure in finite graphs
• Finding Branch-Decompositions and Rank-Decompositions
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XVI: Excluding a non-planar graph
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Rank-width and vertex-minors
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Tangles, tree-decompositions and grids in matroids
• Testing branch-width
• The structure of the models of decidable monadic theories of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cited in

(15)

• Computing height-optimal tangles faster
• Tangles and connectivity in graphs
• Tangle machines
• Tangle and Maximal Ideal
• Rooted grid minors
• Tangles and single linkage hierarchical clustering
• Tangle machines
• Canonisation and Definability for Graphs of Bounded Rank Width
• Computing with Tangles
• Tangle bases: Revisited
• The complexity of finding tangles
• Entanglements
• Point sets and functions inducing tangles of set separations
• Characterising 4-tangles through a connectivity property
• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.

This page was built for publication: Computing with tangles

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