Abstract:
Complexity of the graph isomorphism problem is still an open question. There are no proofs of its NP-completeness or its NP-hardness either. And yet no polynomial-time algorithm for the problem has been designed. We present schemes of algorithms for the graph isomorphism problem. These schemes are based on a successive simplifying tested graphs. Presented algorithms use elements of inverse matrices of the modified graph adjacency matrices as a graph invariant. Results of numerical experiments and computational complexity of the algorithms are considered.