Please use this identifier to cite or link to this item: http://repositorio.ufes.br/handle/10/4257
Title: Um Estudo da Eficiência da Autocentralidade no Problema de Isomorfismo de Grafos
metadata.dc.creator: BARONI, M. D. V.
Keywords: Isomorfismo de grafos;Centralidade de Autovetor;Grafos Reg
Issue Date: 27-Jan-2012
Publisher: Universidade Federal do Espírito Santo
Citation: BARONI, M. D. V., Um Estudo da Eficiência da Autocentralidade no Problema de Isomorfismo de Grafos
Abstract: Este trabalho trata da aplicação da autocentralidade na resolução do Problema de Isomorfismo de Grafos. Esta propriedade, retirada da teoria espectral de grafos, foi utilizada por Philippe Santos em [SANTOS 2010] para a proposta de um algoritmo espectral para resolução deste problema. Uma adaptação do método das potências é proposta para o cálculo das autocentralidades produzindo uma versão competitiva do algoritmo espectral proposto em [SANTOS 2010]. Baseado nesta adaptação, é feito um estudo da eficiência da autocentralidade na resolução do Problema de Isomorfismo. Além disso, é Algoritmo de Rotulação Iterativa Baseado em Medidas de Centralidades, que pode ser aplicado a qualquer tipo de grafo, inclusive grafos regulares. Uma bateria de testes computacionais foi realizada para comparar os dois algoritmos propostos com alguns bemconhecidos na literatura, como o Nauty.
URI: http://repositorio.ufes.br/handle/10/4257
Appears in Collections:PPGI - Dissertações de mestrado

Files in This Item:
File Description SizeFormat 
tese_5124_.pdf876.37 kBAdobe PDFView/Open


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