2 papers
cs.DM2025
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…
cs.DS2024
Forbidden Patterns in Temporal Graphs Resulting from Encounters in a Corridor
Mónika Csikós, Michel Habib, Minh-Hang Nguyen +2
In this paper, we study temporal graphs arising from mobility models, where vertices correspond to agents moving in space and edges appear each time two agents meet. We propose a r…