Projects

Multi-layer and Temporal Graphs

We often encounter relationships between pairs of individuals, like friendship, conflicts, or observed interactions. The basic model for such a relationship is a graph. Often, obtaining useful information about a graph is computationally hard and a lot of algorithmic research focuses on making algorithms for these tasks as efficient as they can be. In applications it now becomes more and more important to incorporate multi-layer and temporal aspects of the relationships. For example, we may want to find communities in a set of people by incorporating multiple relationships as derived from the layers “facebook friendships”, “geographic closeness” and so on. We may want to model communities themselves as the layers that in conjunction lead to set of friendships we can observe on facebook. Or we may want to track communities over time. In the underlying computational problems for such tasks we face new and unique challenges in algorithm design. That’s why I am researching the fundamentals of computational problems for multi-layer and temporal graph problems.

Parameter Hierarchy

A graph parameter is a function assigning an integer to each graph. A graph parameter a can for each graph be smaller than another graph parameter b, it can be always larger or a and b can be incomparable. The relationship between different graph parameters is useful when designing parameterized algorithms. In the graph parameter hierarchy we gather several parameters and their relationships. You can fork the project on gitlab and send me pull requests.