Typical Sequences Revisited — Computing Width Parameters of Graphs

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 bottlene...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2023-02, Vol.67 (1), p.52-88
Main Authors: Bodlaender, Hans L., Jaffke, Lars, Telle, Jan Arne
Format: Article
Language:English
Subjects:
Algorithms
Computer Science
Dynamic programming
Graph theory
Graphs
Polynomials
Run time (computers)
Sequences
Special Issue on Theoretical Aspects of Computer Science (STACS 2020)
Theorems
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-021-10030-3