Mostra i principali dati dell'item
Paralelização do problema de graph matching para grafos exatos utilizando CUDA
| dc.contributor.advisor | Martinotto, André Luis | |
| dc.contributor.author | Lemes, Allan Felipe | |
| dc.contributor.other | Nascimento, Alexandre Erasmo Krohn | |
| dc.contributor.other | Dorneles, Ricardo Vargas | |
| dc.date.accessioned | 2022-03-21T16:55:56Z | |
| dc.date.available | 2022-03-21T16:55:56Z | |
| dc.date.issued | 2020-12-24 | |
| dc.date.submitted | 2020-12-03 | |
| dc.identifier.uri | https://repositorio.ucs.br/11338/9705 | |
| dc.description | O problema de graph matching aplicado a grafos exatos consiste em achar a similaridade entre dois grafos, definindo se estes possuem uma similaridade por completo (grafos isomorfos) ou se existe algum subgrafo similar (subgrafos isomorfos). Ainda não foi determinado se esse problema pertence à classe P ou NP-Completo, não existindo algoritmos polinomiais para a solução do mesmo. Desta forma, frequentemente são utilizadas heurísticas para a solução, sendo que entre essas destacam-se o VF2. Dentro deste contexto, neste trabalho foi desenvolvida uma implementação paralela da heurística VF2. Essa foi desenvolvida utilizando a biblioteca CUDA, de forma a explorar o paralelismo em GPUs. Para os testes, foram gerados grafos com três tamanhos distintos, sendo eles: grafos pequenos de 4 vértices, grafos médios com 8 vértices e grafos grandes com 12 vértices. A partir dos testes realizados verificou-se que versão paralela, utilizando grafos pequenos, médios e grande é, respectivamente, 1,66, 1,44 e 1,38 mais rápida que a versão sequencial. [resumo fornecido pelo autor] | pt_BR |
| dc.language.iso | pt | pt_BR |
| dc.subject | Computação | pt_BR |
| dc.subject | Computação gráfica | pt_BR |
| dc.subject | Teoria dos grafos | pt_BR |
| dc.title | Paralelização do problema de graph matching para grafos exatos utilizando CUDA | pt_BR |
| dc.type | Monografia | pt_BR |
| mtd2-br.advisor.instituation | Universidade de Caxias do Sul | pt_BR |
| mtd2-br.program.name | Bacharelado em Ciência da Computação | pt_BR |
| mtd2-br.campus | Campus Universitário de Caxias do Sul | pt_BR |
