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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorRibeiro, Celso da Cruz Carneiro-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3614186131432854-
Autor(es): dc.contributorBuriol, Luciana Salete-
Autor(es): dc.contributorhttp://lattes.cnpq.br/8337454058604654-
Autor(es): dc.contributorResende, Maurício Guilherme de Carvalho-
Autor(es): dc.contributorBoeres, Maria Cristina Silva-
Autor(es): dc.contributorhttp://lattes.cnpq.br/0306766365983082-
Autor(es): dc.contributorMartins, Simone de Lima-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5202429302236084-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2583204549532431-
Autor(es): dc.creatorToso, Rodrigo Franco-
Data de aceite: dc.date.accessioned2024-07-11T17:48:03Z-
Data de disponibilização: dc.date.available2024-07-11T17:48:03Z-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2008-06-24-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2006-08-07-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/17908-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/757757-
Descrição: dc.descriptionO 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-
Descrição: dc.descriptionConselho Nacional de Desenvolvimento Cientifico e Tecnológico-
Descrição: dc.descriptionThe Dynamic Minimum Spanning Tree Problem (DMSTP) is that of maintaining a minimum spanning tree (MST) of a dynamically changing graph, where these changes (or operations) can be insertions and deletions of vertices, insertions or deletions of edges, and modifications of edge weights. The problem is said to be fully dynamic if both insertion and deletion operations are allowed (or if the edge weights can increase or decrease). Otherwise, the problem is said to be partially dynamic or semi dynamic if only one kind of operation is allowed (either edge deletions or insertions, either weight increases or decreases). Also, the problem is said to be on-line if the dynamic changes must be processed in real time (i.e. there is no preprocessing and updates are performed one by one). The study of dynamic graph algorithms, in particular those for maintaining a minimum spanning tree of a dynamically changing graph, is motivated by both practical and theoretical reasons. Dynamic algorithms and data structures can be used in a wide range of real-life problems, e.g. in network-related problems (computer, telephony and cable-TV networks), metaheuristics and local search heuristics. In this work, we make a step toward the experimental evaluation of algorithms to update a minimum spanning tree after edge weight changes. Such algorithms are particularly helpful in the implementation of metaheuristics and local search heuristics for solving broadcast optimization and design problems in communication networks, similar to the algorithms involving dynamic shortest path problems studied by Buriol et al. [6, 7, 8, 9] in the context of the weight setting problem in OSPF/IS-IS routing. Complementary, we propose and evaluate both a new algorithm and a new data structure specifically designed for the edge weight updating variant of the DMSTP. The new algorithm is quite simple to implement and can be used with any data structure for dynamic trees representation-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherPrograma de Pós-Graduação em Computação-
Publicador: dc.publisherComputação-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectCiência da computação-
Palavras-chave: dc.subjectAlgoritmo-
Palavras-chave: dc.subjectAnálise experimental de algoritmos-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectGrafos dinâmicos-
Palavras-chave: dc.subjectComplexidade computacional-
Palavras-chave: dc.subjectÁrvore geradora mínima-
Palavras-chave: dc.subjectÁrvore geradora de custo mínimo-
Palavras-chave: dc.subjectMinimum spanning trees-
Palavras-chave: dc.subjectMinimum weight spanning trees-
Palavras-chave: dc.subjectDynamic graphs-
Palavras-chave: dc.subjectExperimenal analysis of algorithms-
Palavras-chave: dc.subjectComputational complexity-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO-
Título: dc.titleAlgoritmos para atualização de árvores geradoras mínimas em grafos dinâmicos-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.