Teoria espectral de grafos aplicada ao problema de isomorfismo de grafos

Detalhes bibliográficos
Ano de defesa:	2010
Autor(a) principal:	Santos, Philippe Leal Freire dos
Orientador(a):	Não Informado pela instituição
Banca de defesa:	Não Informado pela instituição
Tipo de documento:	Dissertação
Tipo de acesso:	Acesso aberto
Idioma:	por
Instituição de defesa:	Universidade Federal do Espírito Santo BR Mestrado em Informática Centro Tecnológico UFES Programa de Pós-Graduação em Informática
Programa de Pós-Graduação:	Não Informado pela instituição
Departamento:	Não Informado pela instituição
País:	Não Informado pela instituição
Palavras-chave em Português:	Graph isomorphism problem Spectral graph theory Eigenvector centralities Problema de isomorfismo de grafos Teoria espectral de grafos Centralidades de autovetor Teoria dos grafos Teoria espectral (Matemática) Isomorfismos (Matemática) Autovetores Ciência da Computação 004
Link de acesso:	http://repositorio.ufes.br/handle/10/6388
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.

Registros relacionados