| publication name | New Subgraph Isomorphism Algorithms: Vertex versus Path-at-a-time Matching. arXiv preprint arXiv:1904.08819 |
|---|---|
| Authors | Mosab Hassaan & Karam Gouda |
| year | 2019 |
| keywords | |
| journal | arXiv preprint arXiv:1904.08819 |
| volume | Not Available |
| issue | Not Available |
| pages | Not Available |
| publisher | Not Available |
| Local/International | International |
| Paper Link | Not Available |
| Full paper | download |
| Supplementary materials | Not Available |
Abstract
Graphs are widely used to model complicated data semantics in many application domains. In this paper, two novel and efficient algorithms Fast-ON and Fast-P are proposed for solving the subgraph isomorphism problem. The two algorithms are based on Ullman algorithm [Ullmann 1976], apply vertex-at-a-time matching manner and path-at-a-time matching manner respectively, and use effective heuristics to cut the search space. Comparing to the well-known algorithms, Fast-ON and Fast-P achieve up to 1-4 orders of magnitude speed-up for both dense and sparse graph data.