Show simple item record

dc.contributor.authorEiben, Eduard
dc.contributor.authorGanian, Robert
dc.contributor.authorHamm, Thekla
dc.contributor.authorJaffke, Lars
dc.contributor.authorKwon, O-joung
dc.date.accessioned2023-01-04T13:38:35Z
dc.date.available2023-01-04T13:38:35Z
dc.date.created2023-01-03T09:40:22Z
dc.date.issued2022
dc.identifier.issn1868-8969
dc.identifier.urihttps://hdl.handle.net/11250/3040986
dc.description.abstractAlgorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify ℱ-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of ℱ-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can approximate every possible ℱ-branchwidth, providing a unifying parameterized framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions.en_US
dc.language.isoengen_US
dc.publisherDagstuhl Publishingen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/deed.no*
dc.titleA Unifying Framework for Characterizing and Computing Width Measuresen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2022 The Author(s)en_US
cristin.ispublishedtrue
cristin.fulltextoriginal
cristin.qualitycode1
dc.identifier.doi10.4230/LIPIcs.ITCS.2022.63
dc.identifier.cristin2099349
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.source.pagenumber63:1-63:23en_US
dc.identifier.citationLeibniz International Proceedings in Informatics. 2022, 215, 63:1-63:23.en_US
dc.source.volume215en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal