Algoritmos para atualização de árvores geradoras mínimas em grafos dinâmicos

Abstract

O Problema das Árvores Geradoras Mínimas Dinâmicas (PAGMD) tem como objetivo a manutenção de uma árvore geradora mínima de um grafo sujeito a constantes mudanças estruturais, onde tais mudanças podem ser inserções ou remoções de vértices, inserções ou remoções de arestas e modificações em custos de arestas. Este problema é dito totalmente dinâmico quando ambas as operações de inserção e remoção (ou de incremento e decremento em custos de arestas) são permitidas. Por outro lado, este problema é dito parcialmente dinâmico ou semi-dinâmico quando apenas um tipo de operação é permitido (inserções ou remoções, incrementos ou decrementos). Ainda, o problema é dito on-line quando as alterações dinâmicas são processadas em tempo real, ou seja, sem qualquer tipo de pré-processamento. O estudo de algoritmos para grafos dinâmicos, em particular aqueles para a manutenção da árvore geradora mínima de um grafo em constante atualização, é motivado tanto por razões teóricas quanto por razões práticas. Algoritmos e estruturas de dados dinâmicas podem ser utilizados em uma vasta coleção de problemas cotidianos, a citar problemas de otimização em redes (redes de computadores, telefonia e TV a cabo), metaheurísticas e heurísticas de busca local. Neste trabalho é realizada uma avaliação experimental dos algoritmos para atualização da árvore geradora mínima de um grafo sujeito a alterações dinâmicas nos custos de suas arestas. Tais algoritmos podem ser úteis na implementação de metaheurísticas e heurísticas de busca local para problemas de projeto e otimização de redes de comunicação, de maneira similar aos algoritmos envolvendo os problemas de caminho mínimo estudados por Buriol et al. [6, 7, 8, 9] no contexto do problema de atribuição de custos para o roteamento de pacotes em redes OSPF/IS-IS. Complementarmente, são propostos um algoritmo e uma estrutura de dados especificamente desenvolvidos para o caso de atualização em custos de arestas. O algoritmo proposto é de simples implementação computacional, podendo ser utilizado com qualquer estrutura de dados para representação de árvores dinâmicas