Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00139
Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs
Donatello Conte,
Pasquale Foggia, and
Mario Vento
Vol. 11, no. 1, pp. 99-143, 2007. Regular paper.
Abstract Graphs are an extremely general and powerful data structure. In pattern
recognition and computer vision, graphs are used to represent
patterns to be recognized or classified. Detection of maximum
common subgraph (MCS) is useful for matching, comparing and
evaluate the similarity of patterns. MCS is a well known
NP-complete problem for which optimal and suboptimal algorithms
are known from the literature. Nevertheless, until now no effort
has been done for characterizing their performance. The lack of a
large database of graphs makes the task of comparing the
performance of different graph matching algorithms difficult, and
often the selection of an algorithm is made on the basis of a few
experimental results available. In this paper, three optimal and
well-known algorithms for maximum common subgraph detection are
described. Moreover a large database containing various categories
of pairs of graphs (e.g. random graphs, meshes, bounded valence
graphs), is presented, and the performance of the three algorithms
is evaluated on this database.
|
Journal Supporters
|