MAC0499 - Trabalho de Conclusão de Curso

Detalhamento

• A1: Revisar a implementação do algoritmo de Holm et al para conexidade em florestas dinâmicas, que foi realizada durante a disciplina de Estruturas de Dados Avançadas [2] oferecida em 2023.
• A2: estudar o capítulo 4 da dissertação de mestrado do Arthur Henrique Dias Rodrigues [3], que descreve o algoritmo de conexidade em grafos dinâmicos utilizando a implementação de florestas dinâmicas.
• A3: implementar o algoritmo estudado em A2 usando a implementação revisada em A1.
• A4: estudar a seção 4 do artigo de Holm, Lichtenberg e Thorup [4], onde é descrito o algoritmo decremental para árvores geradoras de custo mínimo.
• A5: implementar o algoritmo estudado em A4, que é uma adaptação do algoritmo implementado em A3.
• A6: escrever a parte da monografia sobre:
  • grafos dinâmicos;
  • conexidade dinâmica;
  • o problema da árvore geradora de custo mínimo dinâmico e seu caso particular decremental;
  • o algoritmo implementado para árvore geradora de custo mínimo decremental.
• A7: estudar o algoritmo totalmente dinâmico para árvores geradoras de custo mínimo, que é descrito na seção 5 do artigo de Holm, Lichtenberg e Thorup [4].
• A8: escrever brevemente sobre a parte da monografia estudada em A7.
• A9: finalizar a monografia.