research
∙
02/23/2023
Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters
[Alecu et al.: Graph functionality, JCTB2021] define functionality, a gr...
share
research
∙
11/05/2021
Long paths make pattern-counting hard, and deep trees make it harder
We study the counting problem known as #PPM, whose input is a pair of pe...
research
∙
08/31/2021
Non-homotopic Loops with a Bounded Number of Pairwise Intersections
Let V_n be a set of n points in the plane and let x ∉ V_n. An x-loop is ...
research
∙
07/22/2021
Griddings of permutations and hardness of pattern matching
We study the complexity of the decision problem known as Permutation Pat...
research
∙
03/12/2021
Bears with Hats and Independence Polynomials
Consider the following hat guessing game. A bear sits on each vertex of ...
research
∙
08/11/2020