László Babai's Mathematical Result on Graph Isomorphism

• From: <henry.story@bblfish.net>
• Date: Sat, 7 Nov 2015 09:29:18 +0000
• To: Semantic Web <semantic-web@w3.org>
• Message-Id: <32FCF4B3-0806-4EAF-8B8D-DDA675A363FF@bblfish.net>

Hi,

  I was pointed to a blog entitled "A Big Result On Graph Isomorphism - Jumping GI down from the nearly-exponential neighborhood to the nearly-polynomial one"

> László Babai is one of the world experts on complexity theory, especially related to groups and graphs. He also recently won the 2015 ACM Knuth Prize, for which we congratulate him.
> Today we wish to discuss a new result that he has announced that will place graph isomorphism almost in polynomial time.
> More exactly László shows that Graph Isomorphism is in Quasipolynomial Time

https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/ 

Does this affect in any way the algorithms on graphs isomorphisms for RDF graphs?

Henry

Received on Saturday, 7 November 2015 09:29:49 UTC