Subgraph isomorphism problem

From Biocrawler, the free encyclopedia.

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(G₁, G₂)
Input: Two graphs G₁ and G₂.
Question: Is G₁ isomorphic to a subgraph of G₂?

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.

Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem.

Wikipedia (http://en.wikipedia.org/wiki/Main_Page) Subgraph_isomorphism_problem (http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem) version history (http://en.wikipedia.org/w/index.php?title=Subgraph_isomorphism_problem&action=history) GNU Free Documentation Lizenz (http://en.wikipedia.org/wiki/Wikipedia:Text_of_the_GNU_Free_Documentation_License) CC-by-sa (http://creativecommons.org/licenses/by-sa/2.5/)

---