Please use this identifier to cite or link to this item: http://repositorio.ufes.br/handle/10/6388
Title: Teoria Espectral de Grafos aplicada ao problema de Isomorfismo de Grafos
metadata.dc.creator: Santos, Philippe Leal Freire dos
Keywords: Problema de Isomorfismo de Grafos;Teoria Espectral de Grafos;Centralidades de autovetor;Graph Isomorphism Problem;Spectral Graph Yheory;Eigenvector centralities
Issue Date: 23-Aug-2010
Publisher: Universidade Federal do Espírito Santo
Citation: SANTOS, Philippe Leal Freire dos. Teoria Espectral de Grafos aplicada ao problema de Isomorfismo de Grafos. 2010. 70 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Espírito Santo, Vitória, 2010.
Abstract: 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
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.
URI: http://repositorio.ufes.br/handle/10/6388
Appears in Collections:PPGI - Dissertações de mestrado

Files in This Item:
File Description SizeFormat 
Dissertacao de Philippe Leal Freire dos Santos.pdf1.19 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.