3 papers
cs.DS2026
Linear Time Subsequence and Supersequence Regex Matching
Antoine Amarilli, Bartlomiej Dudek, Florin Manea +2
It is well-known that checking whether a given string matches a given regular expression can be done in quadratic time and that this cannot be improved to…
cs.DS2025
Cutwidth Bounds via Vertex Partitions
Antoine Amarilli, Benoît Groz
We study the cutwidth measure on graphs and ways to bound the cutwidth of a graph by partitioning its vertices. We consider bounds expressed as a function of two quantities: on the…
cs.DS2024
Edge-Minimum Walk of Modular Length in Polynomial Time
Antoine Amarilli, Benoît Groz, Nicole Wein
We study the problem of finding, in a directed graph, an st-walk of length r mod q which is edge-minimum, i.e., uses the smallest number of distinct edges. Despite the vast literat…