Abstract
To devise a good algorithm for determining if two graphs are isomorphic, is of considerable practical importance, and is also of great theoretical interest due to its relationship to the concept of NP-completeness. There is no known algorithm that determines if two graphs are or are not isomorphic that runs in polynomial time, i.e., it is not known if graph isomorphism is in P. On the other hand, graph isomorphism [] NP but no one has shown that it is NP-complete. In this thesis we will give a polynomial time algorithm O(n⁵), ISO-MT, that seems' to solve the graph isomorphism decision problem correctly for all classes of graphs. Our algorithm is extremely useful from the practical point of view since counter examples (pairs of graphs for which our algorithm fails) will be so rare that ISO-MT can be safely used for any practical application.
Torres Navarro, Luz (1999). A heuristic algorithm for graph isomorphism. Master's thesis, Texas A&M University. Available electronically from
https : / /hdl .handle .net /1969 .1 /ETD -TAMU -1999 -THESIS -T67.