Made available in DSpace on 2016-12-23T14:33:41Z (GMT). No. of bitstreams: 1
Dissertacao de Philippe Leal Freire dos Santos.pdf: 1222437 bytes, checksum: 0b5ab3d6e8b9f4b4640e53168b2d042d (MD5)
Previous issue date: 2010-08-23 / In this work we investigated the use of concepts from Spectral Graph Theory (SGT) to support the construction of algorithms that solve the Graph Isomorphism Problem (GIP). Three theoretical results which consider information from the spectrum of the graphs and from the eigenvector centralities were presented. Furthermore, an algorithm for detection of graph isomorphism based on two of these results was proposed. Finally, we present the computational results comparing this algorithm with others from literature. / Neste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram apresentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace2.ufes.br:10/6388 |
| Date | 23 August 2010 |
| Creators | Santos, Philippe Leal Freire dos |
| Contributors | Rangel, Maria Cristina, Catabriga, Lúcia, Abreu, Nair Maria Maia de, Boeres, Maria Claudia Silva |
| Publisher | Universidade Federal do Espírito Santo, Programa de Pós-Graduação em Informática, UFES, BR, Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | text |
| Source | reponame:Repositório Institucional da UFES, instname:Universidade Federal do Espírito Santo, instacron:UFES |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds