Graph matching using a direct classification of node attendance

PATTERN RECOGNITION

卷:29

Article

Depiero, F ; Trivedi, M ; Serbin, S

关键词: direct classification;    graph isomorphism;    subgraph isomorphism;    graph matching;    object recognition;   

DOI  :  10.1016/0031-3203(95)00140-9

来源: Elsevier

【 摘 要 】

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. (C) 1996 Pattern Recognition Society. Published by Elsevier Science Ltd.

【 授权许可】

Free