|
Efficient Algorithm for Graph Isomorphism ProblemEasyChair Preprint 798, version historyVersion | Date | Pages | Version notes |
---|
1 | March 1, 2019 | 4 | | 2 | November 16, 2019 | 6 | - The results are formalized with statement of 4 other lemmas.
- Minor corrections are incorporated
| 3 | January 15, 2020 | 8 | (1) The case of non-distinct eigenvalues of adjacency matrix is considered and new ideas are presented (2) Several new references are added (3) Computational Complexity of the algorithm is presented clearly | 4 | January 31, 2020 | 10 | (1) Connections of the isomorphism problem to solution of Algebraic Riccati equation is discussed. Solution in a special case is also provided (2) Sub section on GRAPH SPECTRA is also included (3) Some new references are provided | 5 | March 2, 2020 | 13 | (1) A new lemma ( lemma 5 ) which is crucial for the goodness of algorithm is proved and included (2) Some minor mistakes are corrected (3) Acknowledgements are updated | 6 | May 29, 2022 | 7 | Some results which are not correct are removed. A new algorithm for testing graph isomorphism is provided. Some Lemmas which are not true are removed | 7 | September 9, 2022 | 7 | The abstract is modified with necessary and sufficient conditions for graph isomorphism. Proof of Lemma 2 is made complete formally Lemma 3 is changed into Theorem. This theorem provides a proof of necessary and sufficient conditions for graph isomorphism | 8 | October 6, 2023 | 10 | Polynomial time algorithm to test isomorphism of arbitrary graphs ( with out any conditions ) is proposed. Some mistakes in the earlier versions are corrected. Connections to algebraic Ricatti equation are discussed | 9 | October 23, 2023 | 11 | 1. It is proved that the algorithm meets a lower bound on computational complexity for the graph isomorphism problems. New LEMMA 3 is added 2. Some typos are corrected 3. Section 4 is improved | 10 | November 19, 2023 | 11 | 1. A new lemma i.e. LEMMA 3 is added which provides necessary and sufficient condition for graph isomorphism 2. Using the new Lemma 3, a polynomial time algorithm to check the necessary condition is discussed 3. Some mistakes in the earlier version are corrected |
Keyphrases: Eigenvectors, Permutation Matrices, eigenvalues, isomorphic graphs, spectral representation |
|
|