Maximum Common Subgraph (MCS) Algorithm

From GM-RKB
(Redirected from MCS Algorithm)
Jump to navigation Jump to search

A Maximum Common Subgraph (MCS) Algorithm is a graph matching algorithm that can be implemented by an MCS system to solve an MCS task.



References

2018

2007

Inputs: A pair of graphs, [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math], and a positive integer [math]\displaystyle{ k }[/math].
Question: Do [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math] have a common subgraph of order [math]\displaystyle{ k }[/math] or more?
MCS finds application in many domains. It has been used in bioinformatics [15], chemistry [9, 10], pattern recognition [3, 8], and a variety of other areas. Unfortunately, MCS is an exceedingly difficult problem, with several well-known NP-complete problems reducing to it. The maximum clique problem, for example, corresponds to the special case in which [math]\displaystyle{ |G_1| = |G_2| }[/math] and [math]\displaystyle{ G_1 }[/math] is complete.

2004

2003

2002a

2002b

1997

1992

1981