Maximum common subgraph isomorphism problem
- Maximum common subgraph isomorphism problem
-
In 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:
Maximum common subgraph-isomorphism(G1, G2)
- Input: Two graphs G1 and G2.
- Question: What is the largest induced subgraph of G1 isomorphic to an induced subgraph of G2?
The associated decision problem, i.e., given G1, G2 and an integer k, deciding whether G1 contains an induced subgraph of at least k edges isomorphic to an induced 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
Wikimedia Foundation.
2010.
Look at other dictionaries:
Subgraph isomorphism problem — In 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.Subgraph Isomorphism(G1, G2) Input: Two graphs G1 and G2. Question: Is G1 isomorphic to … Wikipedia
List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… … Wikipedia
NP-complete — Euler diagram for P, NP, NP complete, and NP hard set of problems In computational complexity theory, the complexity class NP complete (abbreviated NP C or NPC) is a class of decision problems. A decision problem L is NP complete if it is in the… … Wikipedia
List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
Modular product of graphs — The modular product of graphs. In graph theory, the modular product of graphs G and H is a graph such that the vertex set of the modular product of G and H is the cartesian product V(G) × V(H); and any two vertices (u, v) and (u… … Wikipedia
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia
Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… … Wikipedia
