A heuristic algorithm for graph isomorphism

Due to the character of the original source materials and the nature of batch digitization, quality control issues may be present in this document. Please report any quality issues you encounter to digital@library.tamu.edu, referencing the URI of the item.Includes bibliographical references (leaves 84-86).Issued also on microfiche from Lange Micrographics.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