Graph matching using a direct classification of node attendance

摘要

An algorithm has been developed that finds isomorphisms between both graphs and subgraphs. The development is introduced in the object recognition problem domain. The method isolates matching subgraphs, finds a node-to-node mapping and reorders nodes, thus permitting a direct comparison to be made between the resultant graphs. The algorithm is of polynomial order. It yields approximate results, maintaining a performance level for subgraph isomorphisms at or above 95% under a wide variety of conditions and with varying levels of noise. The performance on the full size comparisons associated with graph isomorphisms has been found to be 100100, also under a variety of conditions. Performance metrics, methods of testing and results are presented.