Longest Path Subgraph: A Novel and Efficient Algorithm to Match RDF Graphs
Claudio Gutiérrez-Soto, Pedro G. Campos, Julio Águila · 2008
This work presents a new algorithm to detect RDF graph isomorphism. Furthermore, we show that isomorphic RDF graphs issue can be solved in an efficient manner using graphs information. Algorithm efficiency resides in the detection of RDF subgraphs isomorphism. The theoretical complexity of algorithm is O(nlogn+ eG), where n is the number of vertices and eG is the cost to check all edges. The proposed algorithm was compared with Iterative Vertex Classification algorithm in order to show the strengths of the new algorithm, called LPS (Longest Path Subgraph). Experimental tests show a much better performance of LPS algorithm.