Um Novo Algoritmo de Refinamento Para Testes de Isomorfismo em Grafos

Mateus OliveiraFabíola Greve

The graph isomorphism is a fundamental problem but hard to betreated. In practice, heuristics are used to solve such problem in a sactifatorialway. Among these, the most efficient are based in procedures which aimsto group vertices accordingly to their similarities. Such algorithms, called re-finement procedures, are used to reduce the search space of backtracking basedtechniques. For some difficult classes of graphs, the greater the distiction powerof these procedures, the greater the performance of heuristics that uses them.In this work, we propose a new refinement procedure that, besides generalizingknown algorithms, has a power distinction at least equal to them.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: