17 citations · 29 across the 5 of their papers we have counts for
4 papers · 1 filter
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,…
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…
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…