DC Field | Value | Language |
---|---|---|
dc.contributor.author | Diestel, Reinhard | ko |
dc.contributor.author | Oum, Sang-il | ko |
dc.date.accessioned | 2019-10-24T06:20:24Z | - |
dc.date.available | 2019-10-24T06:20:24Z | - |
dc.date.created | 2019-10-22 | - |
dc.date.created | 2019-10-22 | - |
dc.date.issued | 2019-08 | - |
dc.identifier.citation | COMBINATORICA, v.39, no.4, pp.879 - 910 | - |
dc.identifier.issn | 0209-9683 | - |
dc.identifier.uri | http://hdl.handle.net/10203/268047 | - |
dc.description.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. | - |
dc.language | English | - |
dc.publisher | SPRINGER HEIDELBERG | - |
dc.title | Tangle-Tree Duality: In Graphs, Matroids and Beyond | - |
dc.type | Article | - |
dc.identifier.wosid | 000488928800007 | - |
dc.identifier.scopusid | 2-s2.0-85065533307 | - |
dc.type.rims | ART | - |
dc.citation.volume | 39 | - |
dc.citation.issue | 4 | - |
dc.citation.beginningpage | 879 | - |
dc.citation.endingpage | 910 | - |
dc.citation.publicationname | COMBINATORICA | - |
dc.identifier.doi | 10.1007/s00493-019-3798-5 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.contributor.nonIdAuthor | Diestel, Reinhard | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | 05C40 | - |
dc.subject.keywordAuthor | 05C75 | - |
dc.subject.keywordAuthor | 05C83 | - |
dc.subject.keywordPlus | OBSTRUCTIONS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.