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:

Nomeordem decrescente Papel
Maria Claudia Silva Boeres Orientador
Maria Cristina Rangel Co-orientador

Banca:

Nomeordem decrescente Papel
Arlindo Gomes de Alvarenga Examinador Externo
Claudia Marcela Justel Examinador Externo
Maria Claudia Silva Boeres Orientador
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.

Acesso ao documento

Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910