Minimum spanners in temporal graphs

• Grant number: 24/13713-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: November 01, 2024
• End date: October 31, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Fábio Happ Botler
• Grantee: Guilherme Vinicius Ferreira de Assis
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

A temporal graph G* = (G,t) is a graph G in which each edge e is provided with a time interval t(e) which indicates the times when such an edge is available. Such a structure allows us to model situations where the connections between objects vary over time. A temporal path in G* is a path v1 ... vk such that t(v{i-1} vi) <= t(vi t{i+1}), i.e., a path that visits edges in increasing time; and we say that G* is (temporally) connected if for any pair of vertices u,v there is a temporal path in G* starting at u and ending at v. Finally, a spanner in G* is a set of edges of G that induces a spanning subgraph in G and, moreover, is temporally connected. In this project, we explore spanners with a minimum number of edges in temporal graphs.