Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs - Conte, Donatello; Foggia, Pasquale; Vento, Mario (Journal of Graph Algorithms and Applications, 2007)
Graphs are an extremely general and powerful data structure. In patternrecognition and computer vision, graphs are used to representpatterns to be recognized or classified. Detection of maximumcommon subgraph (MCS) is useful for matching, comparing andevaluate the similarity of patterns. MCS is a well knownNP-complete problem for which optimal and suboptimal algorithmsare known from the literature. Nevertheless, until now no efforthas been done for characterizing their performance. The lack of alarge database of graphs makes the task of comparing theperformance of different graph matching algorithms difficult, andoften the selection of an algorithm is made on the basis of a fewexperimental results available. In this paper, three optimal andwell-known algorithms for maximum common subgraph detection aredescribed. Moreover a large database containing various categoriesof pairs of graphs (e.g. random graphs, meshes, bounded valencegraphs), is presented, and the performance of the three algorithmsis evaluated on this database. <!---->