biology daily - the biology and biochemistry encyclopedia
biology daily articles and research Encyclopedia Dictionary Forums biology research links Weblinks Pictures Articles Blogs Newsletter

Subgraph isomorphism problem

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.



07-14-2008 23:18:10
The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License. How to see transparent copy
BiologyDaily.com 2005. Legal info   Privacy