9 citations · 57 across the 31 of their papers we have counts for
43 papers
Computing Ultrabubbles in Linear Time by Reduction to Weak Superbubbles in the Double Covering Graph
Sebastian Schmidt, Juha Harviainen, Corentin Moumard +3
In recent years, in attempts to capture variation structures in genomic and pangenomic graphs, the zoo of bubbles has been filled with more and more different variants. The first m…
Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework
Francisco Sena, Aleksandr Politov, Corentin Moumard +6
A fundamental algorithmic problem in computational biology is to find all subgraphs of a given type (superbubbles, snarls, and ultrabubbles) in a directed or bidirected input graph…
Identifying all snarls and superbubbles in linear-time, via a unified SPQR-tree framework
Francisco Sena, Aleksandr Politov, Corentin Moumard +4
Snarls and superbubbles are fundamental pangenome decompositions capturing variant sites. These bubble-like structures underpin key tasks in computational pangenomics, including st…
Fast and Flexible Flow Decompositions in General Graphs via Dominators
Francisco Sena, Alexandru I. Tomescu
Multi-assembly methods rely at their core on a flow decomposition problem, namely, decomposing a weighted graph into weighted paths or walks. However, most results over the past de…
Maximum Coverage -Antichains and Chains: A Greedy Approach
Manuel Cáceres, Andreas Grigorjew, Wanchote Po Jiamjitrak +1
Given an acyclic digraph and a positive integer , the problem of Maximum Coverage -Antichains (resp. Chains) denoted as MA- (resp. MC-) asks to find set…
Safe Sequences via Dominators in DAGs for Path-Covering Problems
Francisco Sena, Romeo Rizzi, Alexandru I. Tomescu
A path-covering problem on a directed acyclic graph (DAG) requires finding a set of source-to-sink paths that cover all the nodes, all the arcs, or subsets thereof, and additionall…
Width Parameters for Minimum Flow Decomposition
Andreas Grigorjew, Wanchote Jiamjitrak, Brendan Mumey +1
Minimum flow decomposition (MFD) is the strongly NP-hard problem of finding a smallest set of integer weighted - paths in an - DAG whose weighted sum is equal to a…
Accelerating ILP solvers for Minimum Flow Decompositions through search space and dimensionality reductions
Andreas Grigorjew, Fernando H. C. Dias, Andrea Cracco +2
Given a flow network, the Minimum Flow Decomposition (MFD) problem is finding the smallest possible set of weighted paths whose superposition equals the flow. It is a classical, st…
Minimum Path Cover: The Power of Parameterization
Manuel Cáceres, Brendan Mumey, Santeri Toivonen +1
Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) is a fundamental problem with a myriad of applications, including reachability. Although it is known how to s…
A Safety Framework for Flow Decomposition Problems via Integer Linear Programming
Fernando H. C. Dias, Manuel Caceres, Lucia Williams +2
Many important problems in Bioinformatics (e.g., assembly or multi-assembly) admit multiple solutions, while the final objective is to report only one. A common approach to deal wi…
Minimum Path Cover in Parameterized Linear Time
Manuel Caceres, Massimo Cairo, Brendan Mumey +2
A minimum path cover (MPC) of a directed acyclic graph (DAG) is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic…
Cut paths and their remainder structure, with applications
Massimo Cairo, Shahbaz Khan, Romeo Rizzi +3
In a strongly connected graph , a cut arc (also called strong bridge) is an arc whose removal makes the graph no longer strongly connected. Equivalently, there…
Minimum Flow Decomposition in Graphs with Cycles using Integer Linear Programming
Fernando H. C. Dias, Lucia Williams, Brendan Mumey +1
Minimum flow decomposition (MFD) -- the problem of finding a minimum set of weighted source-to-sink paths that perfectly decomposes a flow -- is a classical problem in Computer Sci…
Simplicity in Eulerian Circuits: Uniqueness and Safety
Nidia Obscura Acosta, Alexandru I. Tomescu
An Eulerian circuit in a directed graph is one of the most fundamental Graph Theory notions. Detecting if a graph has a unique Eulerian circuit can be done in polynomial time v…
Width Helps and Hinders Splitting Flows
Manuel Cáceres, Massimo Cairo, Andreas Grigorjew +5
Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation on a directed graph into weighted source-to-sink p…
Safety and Completeness in Flow Decompositions for RNA Assembly
Shahbaz Khan, Milla Kortelainen, Manuel Cáceres +2
Decomposing a network flow into weighted paths has numerous applications. Some applications require any decomposition that is optimal w.r.t. some property such as number of paths,…
Fast, Flexible, and Exact Minimum Flow Decompositions via ILP
Fernando H. C. Dias, Lucia Williams, Brendan Mumey +1
Minimum flow decomposition (MFD) (the problem of finding a minimum set of paths that perfectly decomposes a flow) is a classical problem in Computer Science, and variants of it are…
The Labeled Direct Product Optimally Solves String Problems on Graphs
Nicola Rizzo, Alexandru I. Tomescu, Alberto Policriti
Suffix trees are an important data structure at the core of optimal solutions to many fundamental string problems, such as exact pattern matching, longest common substring, matchin…
Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
Manuel Cáceres, Massimo Cairo, Brendan Mumey +2
A minimum path cover (MPC) of a directed acyclic graph (DAG) is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic…
Algorithms and Complexity on Indexing Founder Graphs
Massimo Equi, Tuukka Norri, Jarno Alanko +3
We study the problem of matching a string in a labeled graph. Previous research has shown that unless the Orthogonal Vectors Hypothesis (OVH) is false, one cannot solve this proble…
Optimizing Safe Flow Decompositions in DAGs
Shahbaz Khan, Alexandru I. Tomescu
Network flow is one of the most studied combinatorial optimization problems having innumerable applications. Any flow on a directed acyclic graph having vertices and ed…
The Hydrostructure: a Universal Framework for Safe and Complete Algorithms for Genome Assembly
Massimo Cairo, Shahbaz Khan, Romeo Rizzi +3
Genome assembly is a fundamental problem in Bioinformatics, requiring to reconstruct a source genome from an assembly graph built from a set of reads (short strings sequenced from…
Safety in - Paths, Trails and Walks
Massimo Cairo, Shahbaz Khan, Romeo Rizzi +2
Given a directed graph and a pair of nodes and , an \emph{- bridge} of is an edge whose removal breaks all - paths of (and thus appears in all -$t…
A linear-time parameterized algorithm for computing the width of a DAG
Manuel Cáceres, Massimo Cairo, Brendan Mumey +2
The width of a directed acyclic graph (DAG) equals the largest number of pairwise non-reachable vertices. Computing the width dates back to Dilworth's and Fulkerso…