Ashay Dharwadker and JohnTagore Tevet
Proceedings of the Institute of Mathematics, Amazon Books, 2009
ISBN 1466394374
We present a new polynomialtime algorithm for determining whether two given graphs are isomorphic or not. We prove that the algorithm is necessary and sufficient for solving the Graph Isomorphism Problem in polynomialtime, thus showing that the Graph Isomorphism Problem is in P. The semiotic theory for the recognition of graph structure is used to define a canonical form of the sign matrix of a graph. We prove that the canonical form of the sign matrix is uniquely identifiable in polynomialtime for isomorphic graphs. The algorithm is demonstrated by solving the Graph Isomorphism Problem for many of the hardest known examples. We implement the algorithm in C++ and provide a demonstration program.
