Notice of RetractionA New Approach of Graph Isomorphism Detection Based on Decision Tree

Notice of Retraction

After careful and considered review of the content of this paper by a duly constituted expert committee, this paper has been found to be in violation of IEEE´s Publication Principles.

We hereby retract the content of this paper. Reasonable effort should be made to remove all past references to this paper.

The presenting author of this paper has the option to appeal this decision by contacting TPII@ieee.org.

A new approach to the problem of graph isomorphism detection base on decision tree is proposed. It is based on the approach proposed by B. T. Messmer and H. Bunke. If the time needed for preprocessing is neglected, the computational complexity of their approach is only polynomial in the number of input graph vertices. However, the decision tree is of exponential size. It´s not practical for the graphs with many vertices. We introduce the vertex invariants to partition the matrix of the input graph before graph isomorphism detection. It can remarkably reduces the size of the decision tree and keeps the same time complexity. Practical experiments with randomly generated graphs were given to prove that.