University of Primorska
Faculty of Mathematics, Natural Sciences and Information Technologies
Datum / Date: 7.3.22
Čas / Time: 10:00 — 11:00
Predavalnica / Location: ZOOM
Predavatelj / Lecturer: Nina Klobas (Durham University)
Naslov / Title: Temporal Graphs
Povzetek / Abstract:
Temporal graphs are graphs with a fixed vertex set and a set of edges that changes over time. This paradigm reflects the structure and operation of a great variety of modern networks, such as social networks, wired or wireless networks whose links change dynamically, transportation networks, etc.
Mainly motivated by the fact that, due to causality, information can be transferred in a temporal graph along sequences of edges whose time-labels are increasing, the most traditional research on temporal graphs has focused on temporal paths and other “path-related” notions, such as e.g. temporal analogues of distance, reachability, and exploration. To complement this direction, several attempts have been recently made to define meaningful “non-path” temporal graph problems, which appropriately model specific applications, such as e.g. temporal analogs of matching, colouring, and vertex covert.
In this talk we will introduce two different problems on temporal graphs (one path-related and one non-path related), and study their complexity.