3 papers
cs.DS2026
Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
Guillaume Aubian, Filippo Brunelli, Feodor F Dragan +4
Temporal graphs arise when modeling interactions that evolve over time. They usually come in several flavors, depending on the number of parameters used to describe the temporal as…
cs.DS2025
Making Temporal Betweenness Computation Faster and Restless
Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot
Buà et al [KDD 2020] recently proved that the problem of computing the betweenness of all nodes of a temporal graph is computationally hard in the case of foremost and fastest pat…
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…