Vis enkel innførsel

dc.contributor.authorPilipczuk, Michal Pawel
dc.date.accessioned2016-06-07T07:30:06Z
dc.date.available2016-06-07T07:30:06Z
dc.date.issued2013
dc.identifier.isbn978-3-939897-50-7
dc.identifier.issn1868-8969
dc.identifier.urihttps://hdl.handle.net/1956/12070
dc.description.abstractThe notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, Scott, and Seymour (Maria Chudnovsky, Alexandra Fradkin, and Paul Seymour, 2012; Maria Chudnovsky, Alex Scott, and Paul Seymour, 2011; Maria Chudnovsky and Paul D. Seymour, 2011; Alexandra Fradkin and Paul Seymour, 2010; Alexandra Fradkin and Paul Seymour, 2011; Ilhee Kim and Paul Seymour, 2012). In this work we introduce a new approach to computing these width measures on semi-complete digraphs, via degree orderings. Using the new technique we are able to reprove the main results of (Maria Chudnovsky, Alexandra Fradkin, and Paul Seymour, 2012; Alexandra Fradkin and Paul Seymour, 2011) in a unified and significantly simplified way, as well as obtain new results. First, we present polynomial-time approximation algorithms for both cutwidth and pathwidth, faster and simpler than the previously known ones; the most significant improvement is in case of pathwidth, where instead of previously known O(OPT)-approximation in fixed-parameter tractable time (Fedor V. Fomin and Michal Pilipczuk, 2013) we obtain a constant-factor approximation in polynomial time. Secondly, by exploiting the new set of obstacles for cutwidth and pathwidth, we show that topological containment and immersion in semi-complete digraphs can be tested in single-exponential fixed-parameter tractable time. Finally, we present how the new approach can be used to obtain exact fixed-parameter tractable algorithms for cutwidth and pathwidth, with single-exponential running time dependency on the optimal width.en_US
dc.language.isoengeng
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY-ND 3.0eng
dc.rights.urihttp://creativecommons.org/licenses/by-nd/3.0/eng
dc.subjectsemi-complete digrapheng
dc.subjecttournamenteng
dc.subjectpathwidtheng
dc.subjectcutwidtheng
dc.titleComputing cutwidth and pathwidth of semi-complete digraphs via degree orderingsen_US
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2016-04-07T06:46:13Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright Michał Pilipczuken_US
dc.identifier.doihttps://doi.org/10.4230/lipics.stacs.2013.197
dc.identifier.cristin1069659
dc.source.journalLeibniz International Proceedings in Informatics
dc.source.pagenumber197-208
dc.subject.nsiVDP::Matematikk og naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Matematisk modellering og numeriske metoder: 427
dc.subject.nsiVDP::Mathematics and natural scienses: 400::Information and communication science: 420::Mathematic modelling and numerical methods: 427
dc.identifier.citationLeibniz International Proceedings in Informatics 2013, 20:197-208
dc.source.volume20


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution CC BY-ND 3.0
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution CC BY-ND 3.0