2026-07-24T09:20:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11918 2024-03-06T10:49:01Z ddc:004 open_access

Typical Sequences Revisited - Computing Width Parameters of Graphs Bodlaender, Hans L. Jaffke, Lars Telle, Jan Arne typical sequences treewidth series parallel digraphs cutwidth modified cutwidth 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 ?(n²) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Lars Jaffke and Jan Arne Telle 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.57 urn:nbn:de:0030-drops-119189 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.57 eng https://creativecommons.org/licenses/by/3.0/legalcode