Generalized Coloring of Permutations: Michal Opler
ICE-TCS seminar
ICE-TCS seminar #321
Date and time: Tuesday, 13 November 2018, 12:10-13:00
Location: Room V1.04
Speaker: Michal Opler (Computer Science Institute, Charles University, Czech Republic)
Title: Generalized Coloring of Permutations
Abstract: A permutation p is a merge of a permutation s and a permutation t, if we can color the elements of p red and blue so that the red elements have the same relative order as s and the blue ones as t. We consider, for fixed hereditary permutation classes C and C, the complexity of determining whether a given permutation p is a merge of an element of C with an element of D.
We develop general algorithmic approaches for identifying polynomially tractable cases of merge
recognition. Our tools include a version of nondeterministic logspace streaming recognizability of
permutations, which we introduce, and a concept of bounded width decomposition, inspired by the work of Ahal and Rabinovich.
