Maximum Coverage k-Antichains and Chains: A Greedy Approach
We obtain fast algorithms for maximum coverage $k$-antichains and chains, and show the limits of the $\texttt{greedy}$ heuristic in these contexts.
Feb 7, 2025
Exploiting uniqueness: seed-chain-extend alignment on elastic founder graphs
We implement a complete seed-chain-extend alignment workflow based on indexable elastic founder graphs (iEFGs). We show how to construct iEFGs from the variations to a linear reference, find high-quality seeds, and extend them using GraphAligner, at the scale of a telomere-to-telomere assembled human chromosome.
Nov 26, 2024
Minimum Path Cover in Parameterized Linear Time
We obtain a new MPC parameterized algorithm for DAGs running in time $O(k^2|V| + |E|)$. Our algorithm is the first solving the problem in parameterized linear time. Additionally, we obtain an edge sparsification algorithm preserving the width of a DAG but reducing $|E|$ to less than $2|V|$. This algorithm runs in time $O(k^2|V|)$ and requires an MPC of a DAG as input, thus its total running time is the same as the running time of our MPC algorithm.
Nov 17, 2022