ICE-TCS seminar: Michal Opler

Solving hard problems effectively on permutations of small grid-width

  • 18.11.2019, 11:50 - 12:35


ICE-TCS seminar #344

Date and time: Monday, 18 November 2019, 11:50-12:35
Location: Room M106
Speaker: Michal Opler
Title: Solving hard problems effectively on permutations of small grid-width

Abstract: From a computer scientist’s point of view, the natural question to ask about permutations is, given permutations p and s, whether p is contained in s. It has been shown by Bose, Buss and Lubiw that this problem, called permutation pattern matching, is NP-complete and there has been a substantial amount of results determining the tractability of its various restricted versions.

In this seminar, we present results that connect the tractability of permutation pattern matching with the structure of permutations p and s. In particular, we introduce a grid-like decomposition of permutations and a corresponding parameter called grid-width, which are well-suited for designing dynamic programming algorithms on permutations. Our main algorithmic contribution is a polynomial time algorithm for computing the longest common subpattern of two permutations given that one of them has bounded grid-width.

We also investigate which permutation classes have bounded grid-width and thus allow for pattern matching in polynomial time.

This is joint work with Vít Jelínek.

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: