Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Cutwidth: Obstructions and Algorithmic Aspects

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:35:49Z
dc.abstract.enCutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most 2^O(k^3*log(k)). As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time 2^O(k^2*log(k))*n, where k is the optimum width and n is the number of vertices. While being slower by a log k-factor in the exponent than the fastest known algorithm, due to Thilikos, Bodlaender, and Serna [J. Algorithms 2005], our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.
dc.affiliationUniwersytet Warszawski
dc.conference.countryDania
dc.conference.datefinish2016-08-26
dc.conference.datestart2016-08-24
dc.conference.placeAarhus
dc.conference.seriesInternational Symposium on Parameterized and Exact Computation (was IWPEC pre 2004)
dc.conference.seriesInternational Symposium on Parameterized and Exact Computation (was IWPEC pre 2004)
dc.conference.shortcutIPEC 2016
dc.conference.weblinkhttps://conferences.au.dk/algo16/ipec/
dc.contributor.authorWrochna, Marcin
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorGiannopoulou, Archontia
dc.contributor.authorThilikos, Dimitrios M.
dc.contributor.authorRaymond, Jean-florent
dc.date.accessioned2024-01-24T21:14:59Z
dc.date.available2024-01-24T21:14:59Z
dc.date.copyright2017-02-09
dc.date.issued2017
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.IPEC.2016.15
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/104053
dc.identifier.weblinkhttp://link.springer.com/article/10.1007/s00453-018-0424-7/fulltext.html
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages15:1--15:13
dc.rightsCC-BY
dc.sciencecloudnosend
dc.subject.encutwidth
dc.subject.enobstructions
dc.subject.enimmersions
dc.subject.enfixed-parameter tractability
dc.titleCutwidth: Obstructions and Algorithmic Aspects
dc.typeJournalArticle
dspace.entity.typePublication