meanings of Subgraph isomorphism problem encyclopedia of Subgraph isomorphism problem dictionary of Subgraph isomorphism problem thesaurus on Subgraph isomorphism problem books about Subgraph isomorphism problem dreams about Subgraph isomorphism problem
 Subgraph isomorphism problem - Definition 

In complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. The formal description of the decision problem is as follows.

Subgraph-Isomorphism(G1, G2)
Input: Two graphs G1 and G2.
Question: Is G1 isomorphic to a subgraph of G2?

Sometimes also name subgraph matching is used for the same problem. This name puts emphasis on finding such a subgraph and is not a bare decision problem.


Copyright 2008 WordIQ.com - Privacy Policy  ::  Terms of Use  :: Contact Us  :: About Us
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Subgraph isomorphism problem".