Return to search

Um Estudo da Eficiência da Autocentralidade no Problema de Isomorfismo de Grafos

Made available in DSpace on 2016-08-29T15:33:17Z (GMT). No. of bitstreams: 1
tese_5124_.pdf: 897407 bytes, checksum: 1226caa82994051427d1a23316335ede (MD5)
Previous issue date: 2012-01-27 / 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.

Identiferoai:union.ndltd.org:IBICT/oai:dspace2.ufes.br:10/4257
Date27 January 2012
CreatorsBARONI, M. D. V.
ContributorsRANGEL, M. C., Alvarenga, A. G., JUSTEL, C. M., BOERES, M. C. S.
PublisherUniversidade Federal do Espírito Santo, Mestrado em Informática, Programa de Pós-Graduação em Informática, UFES, BR
Source SetsIBICT Brazilian ETDs
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formattext
Sourcereponame:Repositório Institucional da UFES, instname:Universidade Federal do Espírito Santo, instacron:UFES
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0019 seconds