Teoria espectral e o problema de isomorfismo de grafos regulares

Detalhes bibliográficos
Ano de defesa:	2011
Autor(a) principal:	Rodrigues, Diego Barcelos
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:	Isomorphism Spectro Eigencentrality Espectro Autocentralidade Isomorfismos (Matemática) Análise espectral Ciência da Computação 004
Link de acesso:	http://repositorio.ufes.br/handle/10/6411
Resumo:	Spectral Graph Theory (SGT) studies graph properties by graph representation matrix and its spectrum. A property from SGT, the eigencentrality, provides an important invariant to Graph Isomorphism Problem: if two graphs are isomorphic, they have proportional eigencentralities. However, this property can not be directly used for solving the Regular Graph Isomorphism Problem (RGIP), as every regular graph has the same eigencentralities. This work presents a strategy for solving the RGIP through the use of eigencentralities to prune the search tree and restricting the possibilities for mapping.

Registros relacionados