Scaling Subgraph Matching by Improving Ullmann Algorithm

Abstract

Graphs are widely used to model complicated data semantics in many application 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-ONL. It utilizes a new search ordering and L-levels of vertex neighborhoods (NL) to confine the search space of Ullmann algorithm. Our performance study shows that Ullmann-ONL outperforms previously proposed algorithms with a wide margin.