GRAPH ISOMORPHISM DETERMINATION DEVICE, GRAPH ISOMORPHISM DETERMINATION METHOD, PROGRAM AND EVALUATION SYSTEM

摘要

PROBLEM TO BE SOLVED: To reliably determine an isomorphism between two graphs within a short period of time.;SOLUTION: A graph isomorphism determination device 100 determines the isomorphism between two graphs each of which comprises a set of plurality of nodes and links connecting the nodes. A tree conversion section 10 gives a class and a rank of each of the plurality of nodes based on the connection relation with other nodes connected by the links, without overlapping among the nodes, and thereby converts the structure of each graph into a tree structure based on the class and the rank of each node. A comparison and determination section 11 compares two graphs converted into the tree structure by the tree conversion section 10 and thereby determines whether or not the two graphs agree with each other.;COPYRIGHT: (C)2012,JPO&INPIT