Temporal queries for dynamic temporal forests

In a temporal forest each edge is associated with a set of time labels, that specify the time instants in which the edge is available. A temporal path from a vertex u to a vertex v in the forest is a selection of a label for each edge in the unique path from u to v, assuming it exists, such that the labels selected for any two consecutive edges are non-decreasing. We design linear-size data structures that maintain a temporal forest of (rooted) trees under addition and deletion of both edge labels and singleton vertices, insertion of root-to-node edges, and removal of edges with no labels. Such data structures can answer temporal reachability, earliest arrival, and latest departure queries. All queries and updates are handled in polylogarithmic worst-case time. Our results can be adapted to deal with latencies (i.e., edge traversal times). More precisely, all the worst-case time bounds are asymptotically unaffected when latencies are uniform. For arbitrary latencies, the update time becomes amortized in the incremental (resp., decremental) case where only label additions (resp., deletions) and edge/singleton insertions (resp., removals) are allowed