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.

Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á eða með því að senda tölvupóst á netfangið:
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our or send an e-mail: