Teoria espectral de grafos aplicada ao problema de isomorfismo de grafos
Nenhuma Miniatura disponível
Data
2010-08-23
Autores
Santos, Philippe Leal Freire dos
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal do Espírito Santo
Resumo
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.
Descrição
Palavras-chave
Graph isomorphism problem , Spectral graph theory , Eigenvector centralities , Problema de isomorfismo de grafos , Teoria espectral de grafos , Centralidades de autovetor
Citação
SANTOS, Philippe Leal Freire dos. Teoria espectral de grafos aplicada ao problema de Isomorfismo de Grafos. 2010. 70 f. Dissertação (Mestrado em Informática) - Universidade Federal do Espírito Santo, Centro Tecnológico, Vitória, 2010.