RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs
Top Cited Papers
- 1 January 2002
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 45 (6) , 631-644
- https://doi.org/10.1093/comjnl/45.6.631
Abstract
A new graph similarity calculation procedure is introduced for comparing labeled graphs. Given a minimum similarity threshold, the procedure consists of an initial screening process to determine whether it is possible for the measure of similarity between the two graphs to exceed the minimum threshold, followed by a rigorous maximum common edge subgraph (MCES) detection algorithm to compute the exact degree and composition of similarity. The proposed MCES algorithm is based on a maximum clique formulation of the problem and is a significant improvement over other published algorithms. It presents new approaches to both lower and upper bounding as well as vertex selection.Keywords
This publication has 0 references indexed in Scilit: