Algoritmos de particionamento de grafos: Um estudo comparativo.
| Autor: | SIQUEIRA, Rafael Mont’Alvão Seixas de |
|---|---|
| Jazyk: | portugalština |
| Rok vydání: | 2017 |
| Zdroj: | Repositório Institucional da UNIFEIUniversidade Federal de ItajubáUNIFEI. |
| Druh dokumentu: | masterThesis |
| Popis: | Submitted by repositorio repositorio (repositorio@unifei.edu.br) on 2017-12-19T15:16:33Z No. of bitstreams: 1 dissertacao_silva4_2017.pdf: 676195 bytes, checksum: 33617c7ab4672f7c325d027786471d95 (MD5) Made available in DSpace on 2017-12-19T15:16:33Z (GMT). No. of bitstreams: 1 dissertacao_silva4_2017.pdf: 676195 bytes, checksum: 33617c7ab4672f7c325d027786471d95 (MD5) Previous issue date: 2017-03 Esta dissertação apresenta um estudo sobre o problema do particionamento de grafos e as soluções mais encontradas na literatura, adaptadas para que o armazenamento de cada instância ocorra em disco. Descreve alguns dos fundamentos referentes a Teoria de Grafos e a Teoria Espectral de Grafos, necessários para a compreensão de cada um dos métodos de particionamento aqui retratados e encontrados de forma mais comum na literatura, bem como o contexto e as vantagens na aplicação de cada um deles. Encontra-se nesta dissertação também um breve estudo sobre bancos de dados não relacionais orientados a grafos, sendo este o recurso escolhido para a gestão de dados em disco adotado para implementações e execuções de testes computacionais, diferente de métodos tradicionais que representam em memória os grafos, sendo limitados ao tamanho deste recurso para trabalhar o número de vértices e arestas, afetando a representação de contextos reais com grandes volumes de dados nos quais o particionamento de grafos são necessários. Finalmente, são apresentados os estudos comparativos entre os algoritmos considerando só aspectos de corte mínimo, fator de balanceamento de carga, coeficiente de agrupamento global e coeficiente de agrupamento local, permitindo algumas conclusões sobre experimentos. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|