Graph Matching Using a Direct Classification of Node Attendance

Fred DePiero, University of Tennessee - Knoxville
Mohan Trivedi, University of Tennessee - Knoxville
Steve Serbin, University of Tennessee - Knoxville

Article comments

The definitive version can be found online at http://dx.doi.org/10.1016/0031-3203(95)00140-9.

NOTE: At the time of publication, the author Fred DePiero was affiliated with University of Tennessee - Knoxville. Currently, August 2008, he is a faculty member in the College of Engineering at California Polytechnic State University - San Luis Obispo.

Abstract

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 100/100, also under a variety of conditions. Performance metrics, methods of testing and results are presented.