TopCoder Forums RSS Feed
http://apps.topcoder.com/forums/
Most recent forum messagesenTue, 23 Jan 2018 04:35:18 -0500Proposed O(N^5) algorithm solving Graph Isomorphism problem
http://apps.topcoder.com/forums/?module=Message&messageID=1486073
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.]]>rsargeMon, 30 Jan 2012 19:19:40 -0500Mon, 30 Jan 2012 19:19:40 -0500Mon, 30 Jan 2012 19:20:22 -0500rsarge0