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
Maximum common subgraph isomorphism problemIn complexity theory, maximum common subgraph-isomorphism (MCS) is an optimization problem that is known to be NP-hard. The formal description of the problem is as follows: Additional recommended knowledgeMaximum common subgraph-isomorphism(G1, G2)
The associated decision problem, i.e., given G1, G2 and an integer k, deciding whether G1 contains a subgraph of at least k edges isomorphic to a subgraph of G2 is NP-complete. One possible solution for this problem is to build a modular product graph, in which the largest clique represents a solution for the MCS problem. MCS algorithms have a long tradition in cheminformatics and pharmacophore mapping. See also
References
|
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Maximum_common_subgraph_isomorphism_problem". A list of authors is available in Wikipedia. |