Orientador: Prof. Dr. Daniel Morgato Martin / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciências da Computação, 2014. / Neste trabalho estudamos o Problema do Isomorfismo de Grafos e a sua complexidade
para resolvê-lo. Nossa principal contribuição é a proposta de um algoritmo
para o caso geral do Problema, baseado no particionamento do conjunto de vértices
e em emparelhamentos perfeitos de grafos bipartidos.
Estudamos também o algoritmo de Brendan McKay, que é o mais rápido algoritmo
para o Problema do Isomorfismo de Grafos conhecido. Ao final, implementamos o
algoritmo proposto nesta dissertação e o algoritmo de McKay.
Após a comparação dos dois algoritmos, verificamos que os resultados obtidos pelo
algoritmo proposto não foram satisfatórios, porém apresentamos possíveis melhorias
de como deixá-lo mais eficiente. / In this work we study the Graph Isomorphism Problem and their complexity to
solve it. Our main contribution is to propose an algorithm for the general case of
the Problem, based on partitioning the set vertex and perfect matchings of bipartite
graphs.
We also studied the Brendan McKay¿s algorithm, who is the fastest algorithm for
the Graph Isomorphism Problem known. At the end, we implemented the algorithm
proposed in this dissertation and McKay¿s algorithm.
After comparison of the two algorithms, we found that the results obtained by the
proposed algorithm were not satisfactory, but improvements are possible as to make
it more efficient.
| Identifer | oai:union.ndltd.org:IBICT/oai:BDTD:75394 |
| Date | January 2014 |
| Creators | Rodrigues, Edilson José |
| Contributors | Martin, Daniel Morgato, Cordeiro, Daniel de Angelis, Hausen, Rodrigo de Alencar |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf, 136 f. : il. |
| Source | reponame:Repositório Institucional da UFABC, instname:Universidade Federal do ABC, instacron:UFABC |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=75394&midiaext=69120, http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=75394&midiaext=69119, Cover: http://biblioteca.ufabc.edu.brphp/capa.php?obra=75394 |
Page generated in 0.002 seconds