Teoria Espectral e o Problema de Isomorfismo de Grafos Regulares

AUTOR(ES)

Diego Barcelos Rodrigues

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

29/08/2011

RESUMO

Spectral Graph Theory (SGT) studies graph properties by graph representation matrix and its spectrum. A property from SGT, the eigencentrality, provides an important invariant to Graph Isomorphism Problem: if two graphs are isomorphic, they have proportional eigencentralities. However, this property can not be directly used for solving the Regular Graph Isomorphism Problem (RGIP), as every regular graph has the same eigencentralities. This work presents a strategy for solving the RGIP through the use of eigencentralities to prune the search tree and restricting the possibilities for mapping

ASSUNTO(S)

isomorfismo espectro autocentralidade isomorphism spectro eigencentrality ciencia da computacao

Documentos Relacionados

• Teoria Espectral de Grafos aplicada ao problema de Isomorfismo de Grafos
• Algoritmos quânticos para o problema do isomorfismo de grafos
• O problema da orientação pfaffiana de grafos
• Grafos Associados aos Emparelhamentos de Arestas de Polígonos Regulares
• Institucionalização das iniciativas socioambientais das organizações: interfaces entre a teoria do desenvolvimento social de Habermas e o isomorfismo da teoria institucional