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.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace2.ufes.br:10/4257 |
| Date | 27 January 2012 |
| Creators | BARONI, M. D. V. |
| Contributors | RANGEL, M. C., Alvarenga, A. G., JUSTEL, C. M., BOERES, M. C. S. |
| Publisher | Universidade Federal do Espírito Santo, Mestrado em Informática, Programa de Pós-Graduação em Informática, UFES, BR |
| Source Sets | IBICT Brazilian ETDs |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | text |
| Source | reponame:Repositório Institucional da UFES, instname:Universidade Federal do Espírito Santo, instacron:UFES |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds