On The Complexity of Maximizing Temporal Reachability via Trip Temporalisation

Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot

We consider the problem of assigning appearing times to the edges of a digraph in order to maximize the (average) temporal reachability between pairs of nodes. Motivated by the app…