Data: 18/05/2022, às 16:00 horas (GMT-3, horário de Brasília).
Título: t-spanners em grafos de grau limitado
Palestrante: Renzo Gonzalo Gómez Diaz (Unicamp)

Resumo: Dado um grafo G e uma constante t, um t-spanner de G é um subgrafo de G onde a distância entre quaisquer par de vertices u e v é no máximo t vezes a distância de u e v em G. O conceito de spanners surgiu no estudo de sistemas distribuídos. Desde então, ele tem encontrado aplicação en diversas áreas como robótica, roteamento, geometría computacional, etc.

No problema do t-spanner mínimo, dado um grafo G, estamos interessados em encontrar um t-spanner de G com o menor número de arestas. Neste seminário nos focaremos na classe dos grafos de grau limitado, e apresentaremos alguns resultados de dificuldade computacional, algoritmos polinomiais, e problemas em aberto para esta classe.

Este é um trabalho em conjunto com: Flávio K. Miyazawa e Yoshiko Wakabayashi