8 citations · 54 across the 39 of their papers we have counts for
25 papers · 1 filter
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…
Solving the Probabilistic Profitable Tour Problem on a Tree
Enrico Angelelli, Renata Mansini, Romeo Rizzi
The profitable tour problem (PTP) is a well-known NP-hard routing problem searching for a tour visiting a subset of customers while maximizing profit as the difference between tota…
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…
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…