4 papers
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.…
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…
Optimal Trajectories in Discrete Space with Acceleration Constraints
Arnaud Casteigts, Matteo De Francesco, Pierre Leone
In the racetrack acceleration model, proposed by Martin Gardner in 1973, each step consists of changing the position of the vehicle by a vector in , with the constrai…
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…