Dr. Mosab abd el-hameed mohamed hassaan :: Publications:

Graphs are vastly used to represent many complex data semantics in several domains. Subgraph isomorphism checking (an NP-complete problem) is a regular operation with this kind of data. In this paper, we propose an improvement of Ullmann algorithm, a well-known subgraph isomorphism checker. Our new algorithm is called Ullmann-ON^L. It utilizes a novel sorting method for query vertices and L-levels of vertex neighborhoods (N^L) to confine the search space of Ullmann algorithm. Our performance study shows that Ullmann-ONL outperforms previously proposed algorithms with a wide margin.