1 citations · 2 across the 15 of their papers we have counts for
19 papers
Linear clique-width and modular decomposition
Robert Brignall, Michal Opler, Vincent Vatter
A hereditary class of graphs has bounded clique-width if and only if its prime members do, but this lifting property fails for linear clique-width. We prove that a hereditary class…
Fast and simple multiplication of bounded twin-width matrices
László Kozma, Michal Opler
Matrix multiplication is a fundamental task in almost all computational fields, including machine learning and optimization, computer graphics, signal processing, and graph algorit…
Inapproximability of Counting Permutation Patterns
Michal Opler
Detecting and counting copies of permutation patterns are fundamental algorithmic problems, with applications in the analysis of rankings, nonparametric statistics, and property te…
Monadic Second-Order Logic of Permutations
Vít Jelínek, Michal Opler
Permutations can be viewed as pairs of linear orders, or more formally as models over a signature consisting of two binary relation symbols. This approach was adopted by Albert, Bo…
Compact representations of pattern-avoiding permutations
László Kozma, Michal Opler
Pattern-avoiding permutations are a central object of study in both combinatorics and theoretical computer science. In this paper we design a data structure that can store any size…
An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
Michal Opler
We present a deterministic comparison-based algorithm that sorts sequences avoiding a fixed permutation in linear time, even if is a priori unkown. Moreover, the dependence…
The Hierarchy of Hereditary Sorting Operators
Vít Jelínek, Michal Opler, Jakub Pekárek
We consider the following general model of a sorting procedure: we fix a hereditary permutation class , which corresponds to the operations that the procedure is allow…
Optimization with pattern-avoiding input
Benjamin Aram Berendsohn, László Kozma, Michal Opler
Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. In this paper we study the effect of permutation pattern-avoidance on the complex…
Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters
Pavel Dvořák, Lukáš Folwarczný, Michal Opler +3
Functionality () is a graph parameter that generalizes graph degeneracy defined by Alecu et al. [JCTB, 2021]. They research the relation of functionality to many othe…
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…
A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes
Vít Jelínek, Michal Opler, Jakub Pekárek
Permutation Pattern Matching (PPM) is the problem of deciding for a given pair of permutations P and T whether the pattern P is contained in the text T. Bose, Buss and Lubiw showed…
Two examples of Wilf-collapse
Michael Albert, Vít Jelínek, Michal Opler
Two permutation classes, the X-class and subpermutations of the increasing oscillation are shown to exhibit an exponential Wilf-collapse. This means that the number of distinct enu…
Wilf collapse in permutation classes
Michael Albert, Vít Jelínek, Michal Opler
For a hereditary permutation class , we say that two permutations and of are Wilf-equivalent in , if has the same numb…
Splittability and 1-amalgamability of permutation classes
Vít Jelínek, Michal Opler
A permutation class is splittable if it is contained in a merge of two of its proper subclasses, and it is 1-amalgamable if given two permutations and in , each with…
Squarability of rectangle arrangements
Matěj Konečný, Stanislav Kučera, Michal Opler +3
We study when an arrangement of axis-aligned rectangles can be transformed into an arrangement of axis-aligned squares in while preserving its structure. We found a…
Major index distribution over permutation classes
Michal Opler
For a permutation the major index of is the sum of all indices such that . It is well known that the major index is equidistributed with the number of in…