Geodesic
Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs
Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 99-143.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00139
Keywords: graph matching, maximum common subgraph, graphs database, performance analysis 
@article{JGAA_2007_11_1_a4,
     author = {Donatello Conte and Pasquale Foggia and Mario Vento},
     title = {Challenging {Complexity} of {Maximum} {Common} {Subgraph} {Detection} {Algorithms:} {A} {Performance} {Analysis} of {Three} {Algorithms} on a {Wide} {Database} of {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {99--143},
     publisher = {mathdoc},
     volume = {11},
     number = {1},
     year = {2007},
     doi = {10.7155/jgaa.00139},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00139/}
}
TY  - JOUR
AU  - Donatello Conte
AU  - Pasquale Foggia
AU  - Mario Vento
TI  - Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2007
SP  - 99
EP  - 143
VL  - 11
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00139/
DO  - 10.7155/jgaa.00139
LA  - en
ID  - JGAA_2007_11_1_a4
ER  - 
%0 Journal Article
%A Donatello Conte
%A Pasquale Foggia
%A Mario Vento
%T Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs
%J Journal of Graph Algorithms and Applications
%D 2007
%P 99-143
%V 11
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00139/
%R 10.7155/jgaa.00139
%G en
%F JGAA_2007_11_1_a4
Donatello Conte; Pasquale Foggia; Mario Vento. Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs. Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 99-143. doi : 10.7155/jgaa.00139. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00139/

Cité par Sources :