Spanners mínimos em grafos temporais

• Processo: 24/13713-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de novembro de 2024
• Data de Término da vigência: 31 de outubro de 2025
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Fábio Happ Botler
• Beneficiário: Guilherme Vinicius Ferreira de Assis
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Palavra(s)-Chave do Pesquisador: cliques temporais | conexidade | grafo temporal | spanner | Grafos e Combinatória

Resumo

Um grafo temporal G* = (G,t) é um grafo G no qual cada aresta e é munida de um intervalo de tempo t(e) que indica os instantes em que tal aresta está disponível. Tal estrutura nos permite modelar situações em que as conexões entre os objetos varia de acordo com o tempo. Um caminho temporal em G* é um caminho v1 v2 ... vk tal que t(v{i-1} vi) <= t(vi v{i+1}), i.e., um caminho que visita arestas com tempo crescentes; e G* é dito (temporalmente) conexo se para qualquer par de vértices u,v há um caminho temporal em G* começando em u e terminando em v. Finalmente, um spanner em G* é um conjunto de arestas de G* que induz um subgrafo gerador em G e, além disso, é temporalmente conexo. Neste projeto investigamos spanners com um menor número de arestas em grafos temporais.