Use este identificador para citar ou linkar para este item: http://repositorio.ufes.br/handle/10/4257
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

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
tese_5124_.pdf876.37 kBAdobe PDFVisualizar/Abrir


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