MAC0499 - Trabalho de Conclusão de Curso

Árvores geradoras de custo mínimo em grafos dinâmicos


Aluno:

Orientadora:


Implementação

O repositório com as implementações pode ser acessado aqui GitHub


Proposta de trabalho

O tema a ser trabalhado é o estudo sobre problemas de conexidade em grafos dinâmicos, em particular o problema da árvore geradora mínima em grafos dinâmicos, desde a descrição de um algoritmo para o problema até a sua implementação em código.

Utilizaremos o algoritmo de florestas dinâmicas de Holm et al para implementar o algoritmo deles de conexidade em grafos dinâmicos e, a partir deste, implementar o algoritmo também deles para árvores geradoras de custo mínimo decremental em grafos ponderados dinâmicos.

Estes assuntos se concentram na resolução de problemas de forma eficiente a partir dos grafos que estão sofrendo alterações, visto que problemas clássicos geralmente se limitam a modelos estáticos, isto é, em grafos que não sofrem alterações no decorrer do tempo.


Detalhamento


Cronograma

Atividade Mar Abr Mai Jun Jul Ago Set Out Nov Dez
A1 X
A2 X X
A3 X X X
A4 X X
A5 X X X
A6 X X X X
A7 X X
A8 X X
A9 X X

Referências bibliográficas