Please use this identifier to cite or link to this item: http://repositorio.ufes.br/handle/10/6411
Title: Teoria Espectral e o Problema de Isomorfismo de Grafos Regulares
Authors: Rodrigues, Diego Barcelos
Keywords: Isomorfismo;Espectro;Autocentralidade;Isomorphism;Spectro;Eigencentrality
Issue Date: 29-Aug-2011
Publisher: Universidade Federal do Espírito Santo
Citation: RODRIGUES, Diego Barcelos. Teoria Espectral e o Problema de Isomorfismo de Grafos Regulares. 2011. 84 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Espírito Santo, Vitória, 2011.
Abstract: 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
URI: http://repositorio.ufes.br/handle/10/6411
Appears in Collections:PPGI - Dissertações de mestrado

Files in This Item:
File SizeFormat 
Dissertacao de Diego Barcelos Rodrigues.pdf424.21 kBAdobe PDFView/Open


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