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 language | English |
|---|---|
| Pages (from-to) | 52–88 |
| Number of pages | 37 |
| Journal | Theory of Computing Systems |
| Volume | 67 |
| Issue number | 1 |
| Early online date | 26 Mar 2021 |
| DOIs | |
| Publication status | Published - Feb 2023 |
Bibliographical note
Funding Information:This work was started when the third author was visiting Universitat Politecnica de Valencia, and part of it was done while the second author was visiting Utrecht University. The first author was partially supported by the Networks project, funded by the Netherlands Organization for Scientific Research (NWO). The second author is supported by the Bergen Research Foundation (BFS).
Publisher Copyright:
© 2021, The Author(s).
Funding
This work was started when the third author was visiting Universitat Politecnica de Valencia, and part of it was done while the second author was visiting Utrecht University. The first author was partially supported by the Networks project, funded by the Netherlands Organization for Scientific Research (NWO). The second author is supported by the Bergen Research Foundation (BFS).
Keywords
- Cutwidth
- Modified cutwidth
- Series parallel digraphs
- Treewidth
- Typical sequences