1. RiUfes
2. CT - Centro Tecnológico
3. PPGI - Programa de Pós-Graduação em Informática
4. PPGI - Dissertações de mestrado

Título:	Um Estudo da Eficiência da Autocentralidade no Problema de Isomorfismo de Grafos
Autor(es):	BARONI, M. D. V.
Orientador:	BOERES, M. C. S.
Coorientador:	RANGEL, M. C.
Palavras-chave:	Isomorfismo de grafos Centralidade de Autovetor Grafos Reg
Data do documento:	27-Jan-2012
Editor:	Universidade Federal do Espírito Santo
Citação:	BARONI, M. D. V., Um Estudo da Eficiência da Autocentralidade no Problema de Isomorfismo de Grafos
Resumo:	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
Aparece nas coleções:	PPGI - Dissertações de mestrado

Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.