Um Estudo da Eficiência da Autocentralidade no Problema de Isomorfismo de Grafos
Nome: MARCOS DANIEL VALADÃO BARONI
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 27/01/2012
Orientador:
Nome | Papel |
---|---|
MARIA CLAUDIA SILVA BOERES | Orientador |
Banca:
Nome | Papel |
---|---|
MARIA CLAUDIA SILVA BOERES | Orientador |
ARLINDO GOMES DE ALVARENGA | Examinador Externo |
CLAUDIA MARCELA JUSTEL | Examinador Externo |
MARIA CRISTINA RANGEL | Coorientador |
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.