8 citations · 54 across the 39 of their papers we have counts for
5 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…
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…
The Probabilistic Profitable Tour Problem under a specific graph structure
Enrico Angelelli, Renata Mansini, Romeo Rizzi
Among the most important variants of the traveling salesman problem (TSP) are those relaxing the constraint that every locus should necessarily get visited, rather taking into acco…