Trabalho de Formatura Supervisionado

Aluno: Felipe Castro de Noronha

Supervisora: Profª. Drª. Cristina Gomes Fernandes

Tema: Link-cut trees e aplicações em estruturas de dados retroativas

Proposta

Introdução

A ideia deste trabalho é a realização de um estudo sobre estruturas de dados retroativas, que permitem modificações e consultas não somente no presente, mas também no passado. Em linhas gerais, podemos dividir este trabalho em três partes principais.

A primeira delas seria o estudo e implementação de uma estrutura de dados chamada link-cut tree, que nos permite manter uma floresta dinâmica, realizando ligações e separações de árvores. Essa estrutura servirá como base para as implementações retroativas a seguir.

Inicialmente, estudaremos a versão retroativa da estrutura de dados union-find, usada para manipular uma coleção de conjuntos disjuntos. A ideia é que possamos realizar a união entre dois conjuntos da coleção em qualquer instante de tempo, assim como consultar se dois elementos faziam parte do mesmo conjunto em um certo instante.

Em seguida, estudaremos a versão retroativa do problema da árvore geradora mínima (minimum spanning tree) de um grafo. Nele, podemos realizar modificações na estrutura do grafo e consultar a sua árvore geradora mínima a qualquer momento.

Tarefas

A realização do trabalho pode ser dividida nas seguintes atividades:

• Estudo e implementação da link-cut tree: apresentada por Sleator e Tarjan (1981), essa estrutura é usada para lidar com florestas dinâmicas, permitindo operações de ligação e separação de duas arvores em tempo O(lg n) amortizado.
• Escrita do capítulo sobre link-cut tree: explicação sobre como fazemos para representar a floresta dinâmica internamente, utilizando a ideia de caminhos preferidos implementados com splay trees.
• Estudo e implementação do union-find retroativo: mostrada por Demaine e Iacono (2007), o union-find retroativo permite consultas e modificações em qualquer instante de tempo em uma estrutura que mantém uma coleção de conjuntos disjuntos.
• Escrita do capítulo sobre union-find retroativo: explicação sobre como fazemos para implementar o union-find retroativo utilizando a link-cut tree.
• Estudo e escrita do capítulo sobre a técnica de square root decomposition: utilizada para fazer com que um conjunto de operações que consumiria tempo O(n) gaste tempo proporcional a O(√N), essa técnica divide a estrutura em blocos.
• Implementação da versão retroativa do problema de minimum spanning tree: apresentada por Andrade Júnior e Duarte Seabra (2020), essa estrutura utiliza a link-cut tree com a técnica de square root decomposition para resolver a versão retroativa do problema de árvore geradora mínima, onde podemos realizar modificações na estrutura do grafo em qualquer instante de tempo, assim como consultar a sua árvore geradora mínima.
• Escrita do capítulo sobre a versão retroativa do problema de minimum spanning tree: além da explicação sobre como a versão retroativa do problema da árvore geradora mínima pode ser implementada, vamos também mostrar a como podemos eliminar a necessidade de sabermos de antemão o número de operações a serem realizadas, uma melhoria no trabalho de Andrade Júnior e Duarte Seabra.
• Caso haja tempo, estudo e implementação de outro problema relacionado ao trabalho: como por exemplo, o trabalho de Sunita e Garg (2019), que mostra como podemos utilizar a ideia de retroatividade para resolver o problema de caminho mínimo em um grafo dinâmico.
• Escrita da introdução e resumo da monografia, assim como preparação de poster e/ou apresentação: detalhes finais do trabalho.

A seguir, temos o cronograma aproximado para a realização das atividades acima, os quadros marcados em verde sinalizam o que já foi realizado.

Resumo

Estruturas de dados retroativas permitem a realização de operações que afetam não somente o estado atual da estrutura, mas também em qualquer um de seus estados passados. Além disso, uma link-cut tree é uma estrutura de dados que permite a manutenção de uma floresta de árvores enraizadas com peso nas arestas, e onde os nós de cada árvore possuem um número arbitrário de filhos. Tal estrutura é muito utilizada como base para o desenvolvimento de estruturas de dados retroativas, e neste trabalho estudaremos as versões retroativas dos problemas de union-find e floresta geradora mínima. Para isso, implementamos essas estruturas em \texttt{C++} e descrevemos as ideias por trás de seus funcionamentos. Ademais, apresentamos uma melhoria da solução originalmente apresentada para a floresta geradora mínima retroativa, que retira limitações sem piorar sua performance.