Non-stop propagation in a temporal graph (copie 1)

Speaker: Binh-Minh Bui-Xuan (LIP6)

Room: B512

Date: 11/03/2024 14:00

Abstract:

Path algorithms allow to answer to many fundamental queries on graphs and networks such as accessibility, optimality of a path, natural referencing of a node (SEO), and so on. Applied to graphs whose edges evolve over time, they relate to the propagation of information e.g. in inbound marketing. Two aspects specific to such a use case are temporal path continuity and limited node memory.
Continuity here relates to the fact a path cannot go back to the past:time must be non-decreasing when routing a message. The memory limitation is about the transition time of a message on a node: it takes time for a node to be convinced about a message, at the same time, a node will eventually forget about the information it has learnt after a period of time.
In this talk, we will examine several definitions of temporal paths, leading to both polynomial and NP-difficult cases for computing them.