Generalized Coloring of Permutations: Michal Opler

ICE-TCS seminar

  • 13.11.2018, 12:15 - 13:00


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.