3 papers
cs.DS2026
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…
cs.DS2024
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…
q-bio.GN2023
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…