Repositório Digital

A- A A+

Algoritmo distribuído detector de ciclos baseado em busca e difusão

.

Algoritmo distribuído detector de ciclos baseado em busca e difusão

Mostrar registro completo

Estatísticas

Título Algoritmo distribuído detector de ciclos baseado em busca e difusão
Outro título Cycle finder algorithm based in search and diffusing computations
Autor Sklar, Márcio Muccillo
Orientador Geyer, Claudio Fernando Resin
Data 2008
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Processamento distribuido
[en] Computer network
[en] Cycle detection
[en] Diffusing computation
[en] Digraph
[en] Distributed algorithm
[en] Graph search
Resumo O presente trabalho tem como objetivo principal a modelagem de um algoritmo distribuído baseado em busca e difusão para detectar ciclos simples em uma rede de topologia qualquer. Existem, na literatura, uma série de algoritmos de busca em grafos. De acordo com o tipo de estrutura utilizada para armazenamento, a ordem em que o grafo é percorrido é alterada, caracterizando um tipo de busca com aplicações diferentes. Trabalhos prévios definem, em geral, métodos cujo objetivo é a descoberta de rotas acíclicas, caracterizada por cobrir todos os nodos de uma rede conexa, através da formação de uma spanning tree do grafo. Inversamente, este trabalho centra-se na modelagem de um algoritmo distribuído capaz de capturar rotas cíclicas a partir de nodos previamente escolhidos. Para tanto, um modelo simples de difusão, com busca exaustiva de caminhos, é utilizado sobre uma rede, devidamente abstraída por meio de um dígrafo.
Abstract The main goal of this paper is the modelling of a distributed algorithm based in search and diffusion computations in order to detect cycles in any network topology. There are, in the literature, many graph-search algorithms. Each storage structure defines a order in which the graph is traversed and different applications of this search. Previous works define, in general, methods whose goal is the discovery of acyclic routes, carachterized by covering all nodes of a connected network by discovering a spanning tree of the graph. Instead of it, this paper is centered in the modelling of a distributed algorithm able to detect cyclic routes starting of initial nodes previously chosen. In order to perform it, a simple diffusing computation model that searches exaustively paths is utilized in a network, properly represented by a digraph.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/17409
Arquivos Descrição Formato
000673643.pdf (764.4Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.