Title: Algoritmos para conexidade em grafos dinâmicos
Data: 22 de novembro de 2024 – 14h - Auditório Antonio Gilioli, IME/USP
Student: Arthur Henrique Dias Rodrigues

Abstract: Um grafo dinâmico é um grafo que é sujeito a uma série de modificações em sua estrutura, como por exemplo, a adição e remoção de arestas. Essas modificações alteram significativamente a estrutura do grafo e consequentemente propriedades do grafo, como conexidade. Assim há o interesse em estudar estruturas de dados capazes de manter o grafo dinâmico e a responder a consultas sobre essas propriedades de forma eficiente. Essa dissertação aborda os problemas de conexidade em grafos dinâmicos e floresta maximal de peso mínimo em grafos planos ponderados dinâmicos. O primeiro problema visa manter um grafo dinâmico de forma a permitir a inserção e remoção de arestas e, dados dois vértices u e v, responder a consulta “Os vértices u e v estão na mesma componente conexa?” de forma eficiente. Para solucionar esse problema, apresentamos o algoritmo proposto por Holm, de Lichtenberg e Thorup junto às estruturas de dados utilizadas e a elaboração da estrutura de dados Euler tour tree, que resolve esse problema restrito às florestas dinâmicas. O segundo problema visa manter um grafo plano ponderado dinâmico e uma floresta maximal de peso mínimo F desse grafo de forma a permitir a inserção e remoção de arestas, mudança de peso das arestas e a consulta do peso total de F de forma eficiente. Para esse problema, apresentamos a estrutura de dados proposta por Eppstein e outros. Por fim é apresentado o limitante inferior de Ω(lg n) por operação para os problemas estudados.