To use all functions of this page, please activate cookies in your browser.
my.chemeurope.com
With an accout for my.chemeurope.com you can always see everything at a glance – and you can configure your own website and individual newsletter.
 My watch list
 My saved searches
 My saved topics
 My newsletter
Subgraph isomorphism problemIn complexity theory, SubgraphIsomorphism is a decision problem that is known to be NPcomplete. The formal description of the decision problem is as follows. Additional recommended knowledgeSubgraphIsomorphism(G_{1}, G_{2}) Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem. The proof of subgraph isomorphism being NPcomplete is simple and based on reduction of the clique problem. If subgraph isomorphism were polynomial, you could use it to solve the clique problem in polynomial time. Let n be the number of edges in G: you can then run the subgraph isomorphism n2 times (with G_{1} being a clique of size 3 to n, and G_{2} being G) to find the largest clique in G. Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem; if the graph isomorphism problem is NPcomplete, the polynomial hierarchy collapses, so it is suspected not to be. Application areasIn the area of cheminformatics often the term substructure search is used. Typically a query structure is defined as SMARTS, a SMILES extension. Also of main importance to graph grammars. See also
References

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Subgraph_isomorphism_problem". A list of authors is available in Wikipedia. 