6 citations · 7 across the 9 of their papers we have counts for
11 papers
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…
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…
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…
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…
Fast Circular Pattern Matching
Will Solow, Matthew Barich, Brendan Mumey
The Exact Circular Pattern Matching (ECPM) problem consists of reporting every occurrence of a rotation of a pattern in a text . In many real-world applications, specificall…
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…
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…
A Note on Indexing Point Sets for Approximate Bottleneck Distance Queries
Brendan Mumey
The {\em bottleneck distance} is a natural measure of the distance between two finite point sets of equal cardinality, defined as the minimum over all bijections between the point…