Activity: Talk or presentation › Invited talk › Academic
Description
In this talk, we revisit a key element of the currently asymptotic fasters parameterized algorithms for treewidth and pathwidth: typical sequences.These were introduced in 1991, by Lagergren and Arnborg, and independently by Bodlaender and Kloks. We give a structural result on thejoin of typical sequences, which speeds up one step in these algorithms for treewidth and pathwidth, but does not yet give better time bounds. The result is used to obtain polynomial time algorithms for some problems on directed series parallel graphs. The talk also discusses the current (open) status of the parameterized complexity of pathwidth and treewidth. (This is a joint work with Lars Jaffke and Jan Arne Telle.)