JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums TopCoder Cookbook Algorithm Competitions - New Recipes Proposed O(N^5) algorithm solving Graph Isomorphism problem Revision History (1 edit)
 Proposed O(N^5) algorithm solving Graph Isomorphism problem Here I give the algorithm (as a C++ program), but no math proof yet. http://apps.topcoder.com/forums/?module=Thread&threadID=734973&start=0 Please, challenge it first with counterexamples or acknowledge that it passes your tests. I claim that the algorithm solves a formerly unsolved problem in Computer Science: polynomial-time comparison of graphs (given 2 graphs as adjacency matrices, find a permutation for the rows&columns of the second graph so that the permuted adjacency matrix matches the adjacency matrix of the first graph). The key consequence is that Graph Isomorphism problem belongs to computational complexity class P, because there is a polynomial-time algorithm that solves this problem.
 Proposed O(N^5) algorithm solving Graph Isomorphism problem Here I give the algorithm, but no math proof yet. http://apps.topcoder.com/forums/?module=Thread&threadID=734973&start=0 Please, challenge it first with counterexamples or acknowledge that it passes your tests. I claim that the algorithm solves a formerly unsolved problem in Computer Science: polynomial-time comparison of graphs (given 2 graphs as adjacency matrices, find a permutation for the rows&columns of the second graph so that the permuted adjacency matrix matches the adjacency matrix of the first graph). The key consequence is that Graph Isomorphism problem belongs to computational complexity class P, because there is a polynomial-time algorithm that solves this problem.