Abstract

A temporal graph is a graph in which the edge set can change from time to time. The temporal graph exploration problem, TEXP, is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time.In this work, we consider undirected temporal graphs that are connected at each time step. We present an overview of some known results regarding exploration of temporal cycles and grids, as well as new contributions to the theory of TEXP of cycles and grids. Our results can be grouped into two sets. The first set of results concerns TEXP of cycles. In particular, we positively resolve the conjecture of Erlebach et al. stating that temporal cycles of size n with constantly many chords can be explored in O(n) time steps. Moreover, we design a polynomial time dynamic programming algorithm for computing an optimal temporal walk for TEXP on cycles from any start node. We implemented this algorithm and performed a limited empirical evaluation, results of which are also reported in this thesis. Our second set of results extends the algorithm of Erlebach et al. for the exploration of 2×n temporal grids to modified temporal grids that allow some neighboring edges to cross each other.