Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorPilipczuk, Michal
dc.date.accessioned2020-05-14T13:05:10Z
dc.date.available2020-05-14T13:05:10Z
dc.date.issued2019
dc.PublishedFomin V, Pilipczuk M. On width measures and topological problems on semi-complete digraphs. Journal of combinatorial theory. Series B (Print). 2019;138:78-165eng
dc.identifier.issn0095-8956en_US
dc.identifier.issn1096-0902en_US
dc.identifier.urihttps://hdl.handle.net/1956/22270
dc.descriptionUnder embargo until: 2021-02-01
dc.description.abstractThe topological theory for semi-complete digraphs, pioneered by Chudnovsky, Fradkin, Kim, Scott, and Seymour [10], [11], [12], [28], [43], [39], concentrates on the interplay between the most important width measures — cutwidth and pathwidth — and containment relations like topological/minor containment or immersion. We propose a new approach to this theory that is based on outdegree orderings and new families of obstacles for cutwidth and pathwidth. Using the new approach we are able to reprove the most important known results in a unified and simplified manner, as well as provide multiple improvements. Notably, we obtain a number of efficient approximation and fixed-parameter tractable algorithms for computing width measures of semi-complete digraphs, as well as fast fixed-parameter tractable algorithms for testing containment relations in the semi-complete setting. As a direct corollary of our work, we also derive explicit and essentially tight bounds on duality relations between width parameters and containment orderings in semi-complete digraphs.en_US
dc.language.isoengeng
dc.publisherElsevieren_US
dc.rightsAttribution-NonCommercial-NoDerivs CC BY-NC-NDeng
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/eng
dc.titleOn width measures and topological problems on semi-complete digraphsen_US
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2020-02-11T12:35:10Z
dc.description.versionacceptedVersionen_US
dc.rights.holderCopyright 2019 Elsevieren_US
dc.identifier.doihttps://doi.org/10.1016/j.jctb.2019.01.006
dc.identifier.cristin1693114
dc.source.journalJournal of combinatorial theory. Series B (Print)
dc.relation.projectNorges forskningsråd: 263317


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs CC BY-NC-ND
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs CC BY-NC-ND