Teoria espectral e o problema de isomorfismo de grafos regulares
Nenhuma Miniatura disponível
Data
2011-08-29
Autores
Rodrigues, Diego Barcelos
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal do Espírito Santo
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.
Descrição
Palavras-chave
Isomorphism , Spectro , Eigencentrality , Espectro , Autocentralidade
Citação
RODRIGUES, Diego Barcelos. Teoria espectral e o problema de isomorfismo de grafos regulares. 2011. 84 f. Dissertação (Mestrado em Informática) - Universidade Federal do Espírito Santo, Centro Tecnológico, Vitória, 2011.