Typical Sequences Revisited - Algorithms for Linear Orderings of Series Parallel Digraphs
share
In this paper, we show that the Cutwidth, Modified Cutwidth, and Vertex Separation problems can be solved in O(n^2) time for series parallel digraphs on n vertices. To obtain the result, we give a lemma of independent interest on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP '91] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth.
READ FULL TEXT