A consistency rule for graph isomorphism problem
Badreddine Benreguia, Hamamache Kheddouci · 2012
This paper describes an algorithm for graph isomorphism problem. A consistency rule is proposed to detect as soon as possible the isomorphism permutation. The algorithm, called CRGI, tries to find an isomorphism between two input graphs through a backtracking exploration that uses a proposed consistency rule to prune the tree-search. This rule is based on changing cases positions of one adjacency matrix to obtain exactly the second adjacency matrix, according to a permutation that must be defined. If such permutation exists, an isomorphism is detected. The proposed rule is able to prune as early as possible unfruitful branches of the tree-search which leads to reduce the practical time complexity. Experimental results comparing CRGI with other popular algorithms show the effectiveness of CRGI especially for random graphs and trees.