Tangle-Tree Duality: In Graphs, Matroids and Beyond

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 12
  • Download : 0
We apply a recent tangle-tree duality theorem in abstract separation systems to derive tangle-tree-type duality theorems for width-parameters in graphs and matroids.We further derive a duality theorem for the existence of clusters in large data sets. Our applications to graphs include new, tangle-type, duality theorems for tree-width, path-width, and tree-decompositions of small adhesion. Conversely, we show that carving width is dual to edge-tangles. For matroids we obtain a tangle-type duality theorem for tree-width. Our results can also be used to derive short proofs of all the classical duality theorems for width parameters in graph minor theory, such as path-width, tree-width, branch-width and rank-width.
Publisher
SPRINGER HEIDELBERG
Issue Date
2019-08
Language
English
Article Type
Article
Citation

COMBINATORICA, v.39, no.4, pp.879 - 910

ISSN
0209-9683
DOI
10.1007/s00493-019-3798-5
URI
http://hdl.handle.net/10203/268047
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0