5 citations · 13 across the 12 of their papers we have counts for
15 papers
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…
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…
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…
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…
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…
Computing all - bridges and articulation points simplified
Massimo Cairo, Shahbaz Khan, Romeo Rizzi +3
Given a directed graph and a pair of nodes and , an - bridge of is an edge whose removal breaks all - paths of . Similarly, an - articulation po…
Genome assembly, from practice to theory: safe, complete and linear-time
Massimo Cairo, Romeo Rizzi, Alexandru I. Tomescu +1
Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Even though it is one of the key problems in Bioinformatics, it is generally lacking major…
Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics
Romeo Rizzi, Massimo Cairo, Veli Mäkinen +2
Covering alignment problems arise from recent developments in genomics; so called pan-genome graphs are replacing reference genomes, and advances in haplotyping enable full content…
Dynamic Controllability of Conditional Simple Temporal Networks is PSPACE-complete
Massimo Cairo, Romeo Rizzi
Even after the proposal of various solution algorithms, the precise computational complexity of checking whether a Conditional Temporal Network is Dynamically Controllable had stil…
Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks -- Extended version with an Improved Upper Bound --
Massimo Cairo, Carlo Comin, Romeo Rizzi
CSTNs is a constraint-based graph-formalism for conditional temporal planning. In order to address the DC-Checking problem, in [Comin and Rizzi, TIME 2015] we introduced epsilon-DC…
The Complexity of Simulation and Matrix Multiplication
Massimo Cairo, Romeo Rizzi
Computing the simulation preorder of a given Kripke structure (i.e., a directed graph with labeled vertices) has crucial applications in model checking of temporal logic. It am…
Decoding Hidden Markov Models Faster Than Viterbi Via Online Matrix-Vector (max, +)-Multiplication
Massimo Cairo, Gabriele Farina, Romeo Rizzi
In this paper, we present a novel algorithm for the maximum a posteriori decoding (MAPD) of time-homogeneous Hidden Markov Models (HMM), improving the worst-case running time of th…