Distance Based Canonical Labeling Algorithms with Applications to Graph Matching

Grafos são estruturas matemáticas que codificam relações entre pares de objetos, que são normalmente identificados por rótulos. Entretanto, grafos podem representar relacionamentos entre qualquer tipo de objetos e um problema fundamental é determinar se dois grafos são estruturalmente equivalentes. Este problema clássico da teoria dos grafos, chamado isomorfismo de grafos, pode ser atacado com algoritmos de rotulação canônica, que rotulam os vértices de um grafo se baseando completamente na estrutura do grafo e independente da rotulação inicial dos vértices. Uma pergunta mais recente é sobre como alinhar os vértices de dois grafos estruturalmente similares, um problema conhecido como emparelhamento de grafos. Esta dissertação aborda esse problema com algoritmos de rotulação canônica. Em particular, propõe uma nova abordagem baseada apenas em distâncias, que resolve o problema de emparelhamento de grafos sob algumas condições enquanto sempre resolve o problema de isomorfismo em grafos. Duas variações são consideradas e ambas são implementadas e avaliadas em modelos de grafos aleatórios e redes reais, sob um modelo simples de remoção de arestas. Os algoritmos clássicos de rotulação canônica também são avaliados e comparados com a abordagem proposta baseada em distâncias, que tende a ser superior no alinhamento de grafos semelhantes.