Typical Sequences Revisited — Computing Width Parameters of Graphs

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

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

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 polynomial time.

Original languageEnglish
Pages (from-to)52–88
Number of pages37
JournalTheory of Computing Systems
Volume67
Issue number1
Early online date26 Mar 2021
DOIs
Publication statusPublished - Feb 2023

Keywords

  • Cutwidth
  • Modified cutwidth
  • Series parallel digraphs
  • Treewidth
  • Typical sequences

Fingerprint

Dive into the research topics of 'Typical Sequences Revisited — Computing Width Parameters of Graphs'. Together they form a unique fingerprint.

Cite this