Synopsis
The focus of this project shall lie on temporal graphs: We are given a fixed vertex set and discrete time steps such that at each time step we may have another edge set. We aim to develop efficient (parameterized) algorithms for some of the most central problems related to temporal graphs. The topics we study herein are • community detection and clustering, in particular with respect to their evolution over time, • routing problems on temporal graphs or with temporal aspects, • multi-layer graphs and preservation problems. We aim to fill a gap in the current literature by concentrating mostly on exact combinatorial algorithms in the context of parameterized complexity. That is, we study the influence of small parameters on the complexity of our problems. To this end, we need to extend the toolbox of parameterized algorithmics with new approaches that deal with the temporal aspects of the given problems. Using problems from the above contexts in case studies, we aim to identify key properties of temporal graphs that enable or hinder the development of efficient algorithms. That is, we aim to identify important parameters that exhibit the structure of temporal graphs and we want to study the ways in which this structure can be exploited to find efficient algorithms. In this way, we aim to contribute in equal parts to the theory of temporal graphs as well as to practical solutions for temporal graph problems.
