From Static Graph Theory to Temporal Graph Theory

14^th November 2019, 13:00
Viktor Zamaraev
University of Liverpool

Abstract

Temporal graph theory is a rapidly developing emerging area in theoretical computer science. The demand for the new theory comes from applications where the systems are naturally modeled as networks (i.e., graphs). Under the classical approach, the system would be represented as a static network and then analyzed with standard tools from well-developed graph theory. However, for many systems where the interactions between system nodes change over time, the static network model may be restrictive or oversimplifying, as it does not reflect when the interactions between the units happen. A rich and rapidly growing set of modern systems with dynamic interactions includes Internet, mobile-phone networks, ecological networks, social networks, wireless ad hoc networks, transportation networks, etc. A more adequate model for such systems is temporal networks (also known as evolving or time-varying networks), that is networks whose topology discretely changes over time.

While the last decade saw a flurry of applications and research domains motivating the development of the theory of temporal graphs, the theory itself is still in its infancy. One broad direction in the elaboration of temporal graph theory is systematic development and study of natural temporal analogues to classical graph notions and related problems. In this talk, I will give a high-level overview of some recent works in this direction and present some open problems.