Jump to content

Maximum common induced subgraph

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 64.230.105.200 (talk) at 04:50, 6 January 2007 (The output is not YES/NO, so it is not a decision problem, it is an optimization problem.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In complexity theory, Maximum Common Subgraph-Isomorphism (MCS) is an optimization problem that is known to be NP-complete. The formal description of the problem is as follows.

Maximum Common Subgraph-Isomorphism(G1, G2)
Input: Two graphs G1 and G2.
Question: What is the largest subgraph of G1 isomorphic to a subgraph of G2?

One possible solution for this problem is to build a 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

  • Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.4: GT48, pg.202.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Maximum_common_induced_subgraph&oldid=98809386"