文章基本信息

标题：Typical Sequences Revisited - Computing Width Parameters of Graphs
本地全文：下载
作者：Hans L. Bodlaender ; Lars Jaffke ; Jan Arne Telle 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：57:1-57:16
DOI：10.4230/LIPIcs.STACS.2020.57
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：typical sequences; treewidth; series parallel digraphs; cutwidth; modified cutwidth