TEMPOral GRaph ALgorithms and problems – TEMPOGRAL

Graphs are a fundamental modeling tool in science. They have been used for modeling phenomena in fields ranging from statistical physics to communication networks, distributed algorithms, logistics, biology, medicine, and social networks. Despite great successes in these areas, many real-world phenomena are dynamic and fall beyond the expressivity of standard graphs. In the past two decades, increasing interest has been devoted to temporal graphs (also called time-varying, time-dependent, evolving, or simply dynamic), in which the presence of edges and (sometimes) nodes depends on time. The use of temporal graphs in many of the aforementioned fields, led to a proliferation of new concepts and algorithmic questions, some of which are specific and others more general. The aim of our project is to develop a fundamental (domain-independent) theory of temporal graphs, with a focus on characterizing / classifying / solving algorithmic problems which are intrinsically temporal. The project has three axes, which are (1) classification, (2) tractability, and (3) algorithmic techniques.