BROWSE

Related Scientist

Researcher

엄상일
수리 및 계산 과학 연구단
more info

Tangle-Tree Duality: In Graphs, Matroids and Beyond

Cited 0 time in webofscience Cited 0 time in scopus
14 Viewed 0 Downloaded
Title
Tangle-Tree Duality: In Graphs, Matroids and Beyond
Author(s)
Diestel, R; SANG-IL OUM
Publication Date
2019-08
Journal
COMBINATORICA, v.39, no.4, pp.879 - 910
Publisher
SPRINGER
Abstract
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. c 2019 Janos Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg
URI
https://pr.ibs.re.kr/handle/8788114/6456
ISSN
0209-9683
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > Journal Papers (저널논문)
Files in This Item:
Tangle-Tree Duality In Graphs, Matroids and Beyond.pdfDownload

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse