Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.57
URN: urn:nbn:de:0030-drops-119189
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11918/
Bodlaender, Hans L. ; Jaffke, Lars ; Telle, Jan Arne
Typical Sequences Revisited - Computing Width Parameters of Graphs
| pdf-format: |
|
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 𝒪(n²) time.
BibTeX - Entry
@InProceedings{bodlaender_et_al:LIPIcs:2020:11918,
author = {Hans L. Bodlaender and Lars Jaffke and Jan Arne Telle},
title = {{Typical Sequences Revisited - Computing Width Parameters of Graphs}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {57:1--57:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11918},
URN = {urn:nbn:de:0030-drops-119189},
doi = {10.4230/LIPIcs.STACS.2020.57},
annote = {Keywords: typical sequences, treewidth, series parallel digraphs, cutwidth, modified cutwidth}
}
| Keywords: | typical sequences, treewidth, series parallel digraphs, cutwidth, modified cutwidth | |
| Seminar: | 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 04.03.2020 |
