Saturday, 17 November 2007

A Polynominal Time Algorithm for Graph Isomorphism

A Polynominal Time Algorithm for Graph Isomorphism


Algorithms testing two graphs for isomorphism known as yet have exponential worst case complexity. In this paper we propose a new algorithm that has polynomial complexity and constructively supplies the evidence that the graph isomorphism lies in P.

Will be very interesting to see if the algorithm is indeed correct. I wonder how this process works. Do they have millions of comp sci geeks on hand to verify it? I know that these computational complexity problems were the most interesting problems I did in school. Reducing one problem to the other was awesome.

I'm going to try and give it a read if I have some time and brainpower.

No comments: