Typical Sequences Revisited --- Computing Width Parameters of Graphs

DOI10.4230/LIPICS.STACS.2020.57MaRDI QIDQ6318480arXivFDO

Authors Hans L. Bodlaender, Lars Jaffke, Jan Arne Telle

Publication date 9 May 2019

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2020.57

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.DSmath.CO

Abstract: In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in $mathcalO(n^2)$ time.

This page was built for publication: Typical Sequences Revisited --- Computing Width Parameters of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6318480)