Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorPilipczuk, Michal
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.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.rightsAttribution-NonCommercial-NoDerivs CC BY-NC-NDeng
dc.titleOn width measures and topological problems on semi-complete digraphsen_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright 2019 Elsevieren_US
dc.source.journalJournal of combinatorial theory. Series B (Print)
dc.relation.projectNorges forskningsråd: 263317

Files in this item


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