Teoria Espectral de Grafos aplicada ao problema de Isomorfismo de Grafos
AUTOR(ES)
Philippe Leal Freire dos Santos
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
23/08/2010
RESUMO
Neste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram apresentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura
ASSUNTO(S)
centralidades de autovetor problema de isomorfismo de grafos teoria espectral de grafos graph isomorphism problem spectral graph yheory eigenvector centralities ciencia da computacao
Documentos Relacionados
- Teoria Espectral e o Problema de Isomorfismo de Grafos Regulares
- A teoria dos conjuntos nebulosos aplicada ao problema de fluxo maximo
- Algoritmos quânticos para o problema do isomorfismo de grafos
- Contribuições ao estudo de grafos fuzzy : teoria e algoritmos
- 4 - Análise de sensibilidade aplicada ao problema da fratura
