6 papers
Optimal Trajectories in Discrete Space with Acceleration Constraints
Arnaud Casteigts, Matteo De Francesco, Pierre Leone
In a recreational column of the Scientific American, Martin Gardner presented in 1973 a game called \textsc{Racetrack}, consisting of computing an optimal trajectory for a vehicle…
Realization of Temporally Connected Graphs Based on Degree Sequences
Arnaud Casteigts, Michelle Döring, Nils Morawietz
Given an undirected graph , the problem of deciding whether admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al.,…
Dismountability in Temporal Cliques Revisited
Daniele Carnevale, Arnaud Casteigts, Timothée Corsini
A temporal graph is a graph whose edges are available only at certain points in time. It is temporally connected if the nodes can reach each other by paths that traverse the edges…
Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
Arnaud Casteigts, Nils Morawietz, Petra Wolf
A temporal graph is a graph whose edges only appear at certain points in time. Reachability in these graphs is defined in terms of paths that traverse the edges in chronological or…
Freeze-Tag in has Wake-up Time Five
Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille +1
The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of robots, starting from a single active robot. In the basic geometric version, every…
In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs
Arnaud Casteigts, Timothée Corsini, Nils Morawietz
A temporal graph is a graph whose edges appear at certain points in time. These graphs are temporally connected (in class TC) if all vertices can reach each other by temporal paths…