Jump to content

Maximum common induced subgraph

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Joerg Kurt Wegner (talk | contribs) at 20:53, 5 March 2006. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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

Maximum Common Subgraph-Isomorphism(G₁, G₂)
Input: Two graphs G₁ and G₂.
Question: Find the largest subgraph of G₁ isomorphic to a subgraph of G₂?

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 0716710455. A1.4: GT48, pg.202.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Maximum_common_induced_subgraph&oldid=42385302"