4 papers · 1 filter
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…
Temporal Orienteering with Changing Fuel Costs
Timothée Corsini, Timothée Corsini, Jessica Enright +2
The problem Orienteering asks whether there exists a walk which visits a number of sites without exceeding some fuel budget. In the variant of the problem we consider, the cost of…
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…
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…