34 citations · 86 across the 21 of their papers we have counts for
26 papers
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi +2
A temporal graph is a graph in which edges are assigned a time label. Two nodes u and v of a temporal graph are connected one to the other if there exists a path from u to v with i…
Temporalizing digraphs via linear-size balanced bi-trees
Stéphane Bessy, Stéphan Thomassé, Laurent Viennot
In a directed graph on vertex set , a \emph{forward arc} is an arc where . A pair is \emph{forward connected} if there is a directed pat…
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…
Breadth-First Depth-Next: Optimal Collaborative Exploration of Trees with Low Diameter
Romain Cosson, Laurent Massoulié, Laurent Viennot
We consider the problem of collaborative tree exploration posed by Fraigniaud, Gasieniec, Kowalski, and Pelc where a team of agents is tasked to collectively go through all the…
Minimum-Cost Temporal Walks under Waiting-Time Constraints in Linear Time
Filippo Brunelli, Laurent Viennot
In a temporal graph, each edge is available at specific points in time. Such an availability point is often represented by a ''temporal edge'' that can be traversed from its tail o…
Revisiting the Random Subset Sum problem
Arthur da Cunha, Francesco d'Amore, Frédéric Giroire +3
The average properties of the well-known Subset Sum Problem can be studied by the means of its randomised version, where we are given a target value , random variables $X_1, \ld…