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 EDT

This archive was generated by hypermail pre-2.1.9 : Wednesday, 3 September 2003 09:57:55 EDT