Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
We obtain two new MPC parameterized algorithms for DAGs running in time $O(k^2|V|\log(|V|) + |E|)$ and $O(k^3|V| + |E|)$. We also obtain a parallel algorithm running in $O(k^2|V| + |E|)$ parallel steps and using $O(\log(|V|))$ processors (in the PRAM model). We also obtain edge sparsification algorithms preserving the width of the DAG with the same running time as our MPC algorithms.
Jan 9, 2022
A linear-time parameterized algorithm for computing the width of a DAG
We describe an parameterized algorithm to compute the width $k$ of a DAG in time $O(k2^k|E| + k^24^k|V|)$.
Aug 1, 2021
Fast Indexes for Gapped Pattern Matching
We describe indexes for searching large data sets for variable-length-gapped (VLG) patterns. Our best approach provides search speeds several times faster than prior art across a broad range of patterns and texts.
Jan 17, 2020
Faster Repetition-Aware Compressed Suffix Trees Based on Block Trees
New Repetition-Aware Compressed Suffix Tree. Slightly larger than state-of-the-art, but outperforms them in time, often by orders of magnitude.
Oct 7, 2019