Multivariate Algorithmics for Temporal Graph Problems (MATE)

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2017 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 382063982

As in the first project phase, we aim to develop efficient (parameterized) algorithms for central problems related to temporal graphs. Wehave a shift in the topics we plan to study when compared to the first project phase. The topics we want to investigate are- new temporal concepts such as temporal graph classes, parameters, and problem classes;- problems related to journeys and temporal connectivity;- problems related to temporal subgraph detection.We want to extend the current literature by concentrating mostly on exact combinatorial algorithms in the context of multivariate complexity analysis. That is, we want to identify relevant parameterizations and study their influence 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.

• DFG Programme: Research Grants