Multivariate Algorithmics for Temporal Graph Problems (MATE)

点击翻译按钮获取中文摘要

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.