Tangle-Tree Duality: In Graphs, Matroids and Beyond

Cited 10 time in webofscience Cited 12 time in scopus
  • Hit : 439
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorDiestel, Reinhardko
dc.contributor.authorOum, Sang-ilko
dc.date.accessioned2019-10-24T06:20:24Z-
dc.date.available2019-10-24T06:20:24Z-
dc.date.created2019-10-22-
dc.date.created2019-10-22-
dc.date.issued2019-08-
dc.identifier.citationCOMBINATORICA, v.39, no.4, pp.879 - 910-
dc.identifier.issn0209-9683-
dc.identifier.urihttp://hdl.handle.net/10203/268047-
dc.description.abstractWe 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.languageEnglish-
dc.publisherSPRINGER HEIDELBERG-
dc.titleTangle-Tree Duality: In Graphs, Matroids and Beyond-
dc.typeArticle-
dc.identifier.wosid000488928800007-
dc.identifier.scopusid2-s2.0-85065533307-
dc.type.rimsART-
dc.citation.volume39-
dc.citation.issue4-
dc.citation.beginningpage879-
dc.citation.endingpage910-
dc.citation.publicationnameCOMBINATORICA-
dc.identifier.doi10.1007/s00493-019-3798-5-
dc.contributor.localauthorOum, Sang-il-
dc.contributor.nonIdAuthorDiestel, Reinhard-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthor05C40-
dc.subject.keywordAuthor05C75-
dc.subject.keywordAuthor05C83-
dc.subject.keywordPlusOBSTRUCTIONS-
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 10 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0