A Comparison of Algorithms for Maximum Common Subgraph on Randomly Connected Graphs
Lecture notes in computer sciencePublished 1 January 2002Open access
Horst Bunke, Pasquale Foggia, Corrado Guidobaldi, Carlo Sansone, M. Vento
Citations94
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Two exact algorithms for maximum common subgraph detection are described and a database containing randomly connected pairs of graphs, having a maximum common graph of at least two nodes, is presented, and the performance of the two algorithms is evaluated.
Abstract
A graph g is called a maximum common subgraph of two graphs, g 1 and g 2, if there exists no other common subgraph of g 1 and g 2 that has more nodes than g. For the maximum common subgraph problem, exact and inexact algorithms are known from the literature. Nevertheless, until now no effort has been done for characterizing their performance. In this paper, two exact algorithms for maximum common subgraph detection are described. Moreover a database containing randomly connected pairs of graphs, having a maximum common graph of at least two nodes, is presented, and the performance of the two algorithms is evaluated on this database.
Keywords
Computer Science
Principles of Artificial Intelligence
3,336 Citations1982Nils J. Nilsson
This classic introduction to artificial intelligence describes fundamental AI ideas that underlie applications such as natural language processing, automatic programming, robotics, machine vision, automatic theorem proving, and intelligent data retrieval.
Communications of the ACMAlgorithm 457: finding all cliques of an undirected graph
2,451 Citations1973Coen Bron, Joep Kerbosch
Two backtracking algorithms are presented, using a branchand-bound technique [4] to cut off branches that cannot lead to a clique, and generates cliques in a rather unpredictable order in an attempt to minimize the number of branches to be traversed.
Journal of the ACMAn Algorithm for Subgraph Isomorphism
2,252 Citations1976J. R. Ullmann
A new algorithm is introduced that attains efficiency by inferentially eliminating successor nodes in the tree search by means of a brute-force tree-search enumeration procedure and a parallel asynchronous logic-in-memory implementation of a vital part of the algorithm is described.
Handbook of Combinatorial Optimization
1,218 Citations1999Ding‐Zhu Du, Pãnos M. Pardalos
The Maximum Clique Problem
975 Citations1999Immanuel M. Bomze, Marko Budinich +2 more
This paper considers the problem of finding the largest clique in a graph using the notation ES to represent the subset of edges which have both endpoints in clique S, and concludes that the induced graph GS = ( S, ES ) is complete.
Pattern Recognition LettersA graph distance metric based on the maximal common subgraph
737 Citations1998Horst Bunke, Kim Shearer
It is formally shown that the new distance measure is a metric, based on the maximal common subgraph of two graphs, which is superior to edit distance based measures in that no particular edit operations together with their costs need to be defined.
An Improved Algorithm for Matching Large Graphs
343 Citations2001L.P. Cordella, Pasquale Foggia +2 more
An improved version of a graph matching algorithm is presented, which is able to efficiently solve the graph isomorphicism and graph-subgraph isomorphism problems on Attributed Relational Graphs.
Software Practice and ExperienceBacktrack search algorithms and the maximal common subgraph problem
292 Citations1982James J. McGregor
This algorithm has been used successfully as a component of a program for analysing chemical reactions and enumerating the bond changes which have taken place and its use in the problem of finding the maximal common subgraph of two graphs is described.
CALCOLOA note on the derivation of maximal common subgraphs of two directed or undirected graphs
226 Citations1973Giorgio Levi
A technique is described by which this problem of finding maximal common subgraphs of two given graphs can be stated as a problem of deriving maximal compatibility classes and the same technique is shown to apply to the classical subgraph isomorphism problem.
A Database of Graphs for Isomorphism and Sub-Graph Isomorphism Benchmarking
91 Citations2001Pasquale Foggia, Carlo Sansone +1 more
Journal of the American Chemical SocietyComputer-aided interpretation of mass spectra. 20. Molecular structure comparison program for the identification of maximal common substructures
52 Citations1977M. M. CONE, R. Venkataraghavan +1 more
ComputingOn the Minimum Common Supergraph of Two Graphs
46 Citations2000Horst Bunke, Xiaoyi Jiang +1 more
It is shown that minimum common supergraph computation can be solved by means of maximum common subgraph computation, and it will also be shown that for a certain class of cost functions, the concept of graph edit distance is closely related with the minimum commonsupergraph.
ComputingDiscrete Time Relaxation Based on Direct Quadrature Methods for Volterra Integral Equations
15 Citations1999A. Paone, Antonia Vecchio
Discrete-time relaxation methods based on direct quadrature methods for the numerical solution of second kind Volterra systems are proposed and the convergence of the discrete-time iterations is analyzed.