5 papers · 1 filter
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…
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…
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…
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…