Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyOn width measures and topological problems on semi-complete digraphs
| cris.lastimport.scopus | 2024-02-12T20:48:57Z |
| dc.abstract.en | The 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. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.contributor.author | Pilipczuk, Michał |
| dc.contributor.author | Fomin, Fedor V. |
| dc.date.accessioned | 2024-01-25T15:49:30Z |
| dc.date.available | 2024-01-25T15:49:30Z |
| dc.date.issued | 2019 |
| dc.description.finance | Nie dotyczy |
| dc.description.volume | 138 |
| dc.identifier.doi | 10.1016/J.JCTB.2019.01.006 |
| dc.identifier.issn | 0095-8956 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/114899 |
| dc.identifier.weblink | https://api.elsevier.com/content/article/PII:S0095895619300073?httpAccept=text/xml |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.ispartof | Journal of Combinatorial Theory. Series B |
| dc.relation.pages | 78-165 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.subject.en | Tournament |
| dc.subject.en | Semi-complete digraph |
| dc.subject.en | Pathwidth |
| dc.subject.en | Cutwidth |
| dc.subject.en | Topological containment |
| dc.subject.en | Immersion |
| dc.subject.en | Fixed-parameter tractability |
| dc.title | On width measures and topological problems on semi-complete digraphs |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |