1 citations · 2 across the 15 of their papers we have counts for
4 papers · 1 filter
Long paths make pattern-counting hard, and deep trees make it harder
Vít Jelínek, Michal Opler, Jakub Pekárek
We study the counting problem known as #PPM, whose input is a pair of permutations and (called pattern and text, respectively), and the task is to find the number of subseq…
Non-homotopic Loops with a Bounded Number of Pairwise Intersections
Václav Blažej, Michal Opler, Matas Šileikis +1
Let be a set of points in the plane and let . An -loop is a continuous closed curve not containing any point of . We say that two -loops are non-…
Griddings of permutations and hardness of pattern matching
Vít Jelínek, Michal Opler, Jakub Pekárek
We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations (the `text') and (the `pa…
Bears with Hats and Independence Polynomials
Václav Blažej, Pavel Dvořák, Michal Opler
Consider the following hat guessing game. A bear sits on each vertex of a graph , and a demon puts on each bear a hat colored by one of colors. Each bear sees only the hat c…