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, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. The formal description of the decision problem is as follows. Additional recommended knowledgeSubgraph-Isomorphism(G1, G2) 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 NP-complete 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 n-2 times (with G1 being a clique of size 3 to n, and G2 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 NP-complete, 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. |