Scaling Subgraph Matching by Improving Ullmann Algorithm
DOI:
https://doi.org/10.31577/cai_2022_4_1002Keywords:
Subgraph matching, NP-complete, graph databaseAbstract
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.
Downloads
Download data is not yet available.
Downloads
Published
2022-11-09
How to Cite
Gouda, K., Bujdosó, G., & Hassaan, M. (2022). Scaling Subgraph Matching by Improving Ullmann Algorithm. Computing and Informatics, 41(4), 1002–1024. https://doi.org/10.31577/cai_2022_4_1002
Issue
Section
Articles