METHOD OF DETERMINING GRAPH ISOMORPHISM IN POLYNOMIAL-TIME

摘要

Generating a complete graph invariant may be accomplished by initializing each card of an initial message deck to an identity matrix, propagating messages to form a first iteration message deck using a message propagation rule, generating a first iteration codebook using the first iteration message deck, recoding the first iteration message deck using the first iteration codebook, repeating the propagating, generating, and recoding steps for at least a second iteration, concatenating the message decks elementwise to form a final message deck, row sorting the final message deck to form a row sorted message deck, sorting rows of the row sorted message deck to form a table sorted message deck, and sorting cards of the table sorted message deck to form the invariant.