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.
Keywords
Cite this article
@article{cai-5523,
author = {Karam Gouda and Gyöngyi Bujdosó and Mosab Hassaan},
title = {Scaling Subgraph Matching by Improving Ullmann Algorithm},
journal = {Computing and Informatics},
volume = {41},
number = {4},
pages = {1002--1024},
year = {2022},
issn = {1335-9150},
doi = {10.31577/cai_2022_4_1002}
}
TY - JOUR AU - Karam Gouda AU - Gyöngyi Bujdosó AU - Mosab Hassaan TI - Scaling Subgraph Matching by Improving Ullmann Algorithm JO - Computing and Informatics VL - 41 IS - 4 SP - 1002 EP - 1024 PY - 2022 SN - 1335-9150 DO - 10.31577/cai_2022_4_1002 UR - https://doi.org/10.31577/cai_2022_4_1002 KW - Subgraph matching KW - NP-complete KW - graph database ER -
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