W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > June 2003

Re: blank nodes out the wazoo

From: Jeremy Carroll <jjc@hpl.hp.com>
Date: Sat, 14 Jun 2003 23:08:25 +0300
To: w3c-rdfcore-wg@w3.org
Message-Id: <200306142308.25553.jjc@hpl.hp.com>

> BTW, Jeremy, is there an easy and efficient way to use your graph 
> isomorphism algorithm to determine if G1 is isomorphic to a subgraph of G2?

No, Graph Isomorphism is believed to be truely easier than NP; whereas 
subgraph isomorphism is known to be NP

Having said that, the algorithm are referring to is a long way short of the 
state of the art in GI (see nauty)

Jeremy
Received on Saturday, 14 June 2003 17:08:26 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 14:54:06 UTC