25 citations · 71 across the 20 of their papers we have counts for
27 papers
Simple, strict, proper, happy: A study of reachability in temporal graphs
Arnaud Casteigts, Timothée Corsini, Writika Sarkar
Dynamic networks are a complex subject. Not only do they inherit the complexity of static networks (as a particular case); they are also sensitive to definitional subtleties that a…
Giant Components in Random Temporal Graphs
Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi +4
A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős-Rényi…
A Dynamic Data Structure for Temporal Reachability with Unsorted Contact Insertions
Luiz F. Afra Brito, Marcelo Albertini, Arnaud Casteigts +1
Temporal graphs represent interactions between entities over the time. These interactions may be direct (a contact between two nodes at some time instant), or indirect, through seq…
Revisiting the Role of Coverings in Anonymous Networks: Spanning Tree Construction and Topology Recognition
Arnaud Casteigts, Yves Métivier, John Michael Robson
This paper revisits two classical distributed problems in anonymous networks, namely spanning tree construction and topology recognition, from the point of view of graph covering t…
Sharp Thresholds in Random Simple Temporal Graphs
Arnaud Casteigts, Michael Raskin, Malte Renken +1
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is c…
Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
Arnaud Casteigts, Mathieu Raffinot, Mikhail Raskin +1
We study a new version of the Traveling Salesperson Problem, called \VectorTSP, where the traveler is subject to discrete acceleration constraints, as defined in the paper-and-penc…