Scaling Subgraph Matching by Improving Ullmann Algorithm

Authors

  • Karam Gouda Faculty of Computers and Artificial Intelligence, Benha University, Egypt
  • Gyöngyi Bujdosó Faculty of Informatics, University of Debrecen, Hungary
  • Mosab Hassaan Faculty of Science, Benha University, Egypt & Faculty of Informatics, University of Debrecen, Hungary

DOI:

https://doi.org/10.31577/cai_2022_4_1002

Keywords:

Subgraph matching, NP-complete, graph database

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.

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