<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="7.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Badreddine Benreguia</style></author><author><style face="normal" font="default" size="100%">Hamamache Kheddouci</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">A consistency rule for graph isomorphism</style></title><secondary-title><style face="normal" font="default" size="100%">27th ACM Symposium On Applied Computing (SAC2012)</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2012</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">https://dl.acm.org/doi/10.1145/2245276.2245453</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">ACM</style></publisher><pub-location><style face="normal" font="default" size="100%">Italy</style></pub-location><pages><style face="normal" font="default" size="100%">906–911</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">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.</style></abstract></record></records></xml>