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
∙
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
∙
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
∙
10/14/2022
Cut paths and their remainder structure, with applications
In a strongly connected graph G = (V,E), a cut arc (also called strong b...
research
∙
08/31/2022
Minimum Flow Decomposition in Graphs with Cycles using Integer Linear Programming
Minimum flow decomposition (MFD) – the problem of finding a minimum set ...
research
∙
08/17/2022
Simplicity in Eulerian Circuits: Uniqueness and Safety
An Eulerian circuit in a directed graph is one of the most fundamental G...
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
∙
09/11/2021
The Labeled Direct Product Optimally Solves String Problems on Graphs
Suffix trees are an important data structure at the core of optimal solu...
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
∙
02/25/2021
Algorithms and Complexity on Indexing Founder Graphs
We study the problem of matching a string in a labeled graph. Previous r...
research
∙
02/12/2021
Safety of Flow Decompositions in DAGs
Network flows are one of the most studied combinatorial optimization pro...
research
∙
11/25/2020
Genome assembly, a universal theoretical framework: unifying and generalizing the safe and complete algorithms
Genome assembly is a fundamental problem in Bioinformatics, requiring to...
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
∙
07/09/2020
Safety in s-t Paths, Trails and Walks
Given a directed graph G and a pair of nodes s and t, an s-t bridge of G...
research
∙
06/26/2020
Computing all s-t bridges and articulation points simplified
Given a directed graph G and a pair of nodes s and t, an s-t bridge of G...
research
∙
05/19/2020
Linear Time Construction of Indexable Founder Block Graphs
We introduce a compact pangenome representation based on an optimal segm...
research
∙
02/24/2020
From omnitigs to macrotigs: a linear-time algorithm for safe walks – common to all closed arc-coverings of a directed graph
A partial solution to a problem is called safe if it appears in all solu...
research
∙
02/03/2020
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
We consider the following string matching problem on a node-labeled grap...
research
∙
02/03/2020
Conditional Indexing Lower Bounds Through Self-Reducibility
We provide a general technique to turn a conditional lower bound result ...
research
∙
02/10/2019