Algorithmics and Computational Complexity Research GroupTalk 20.08.2019

# Temporal Graph Exploration: Two Moves per Time Step Make a Difference

Frank Kammer (Technische Hochschule Mittelhessen)



A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex,moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible.

We first present a lower bound of Ω(n2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree [ICALP 2015]. Afterwards, we break this bound and show that every temporal graph with n vertices can be explored in O(n1.75+ε) time steps for arbitrary ε > 0 provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step [ICALP 2019].

Date
Speaker
Location
Language
20.08.2019
17:15
Frank Kammer
TEL 512
English

Back to the research colloquium site.

To top