research
∙
08/17/2023
Minimum Path Cover: The Power of Parameterization
Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) i...
share
research
∙
05/16/2023
Finding Maximal Exact Matches in Graphs
We study the problem of finding maximal exact matches (MEMs) between a q...
research
∙
05/09/2023
Sorting Finite Automata via Partition Refinement
Wheeler nondeterministic finite automata (WNFAs) were introduced as a ge...
research
∙
05/03/2023
Minimum Chain Cover in Almost Linear Time
A minimum chain cover (MCC) of a k-width directed acyclic graph (DAG) G ...
research
∙
02/03/2023
Chaining of Maximal Exact Matches in Graphs
We study the problem of finding maximal exact matches (MEMs) between a q...
research
∙
01/30/2023
A Safety Framework for Flow Decomposition Problems via Integer Linear Programming
Many important problems in Bioinformatics (e.g., assembly or multi-assem...
research
∙
12/15/2022
Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond
The problem of String Matching to Labeled Graphs (SMLG) asks to find all...
research
∙
11/17/2022
Minimum Path Cover in Parameterized Linear Time
A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V,E) i...
research
∙
07/05/2022
Width Helps and Hinders Splitting Flows
Minimum flow decomposition (MFD) is the NP-hard problem of finding a sma...
research
∙
01/25/2022
Safety and Completeness in Flow Decompositions for RNA Assembly
Decomposing a network flow into weighted paths has numerous applications...
research
∙
07/12/2021
Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V,E) i...
research
∙
07/15/2020
On the parameterized complexity of the Minimum Path Cover problem in DAGs
A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V,E) i...
research
∙
02/28/2020
Fast Indexes for Gapped Pattern Matching
We describe indexes for searching large data sets for variable-length-ga...
research
∙
02/08/2019