| You are in:Home/Publications/New Subgraph Isomorphism Algorithms: Vertex versus Path-at-a-time Matching. arXiv preprint arXiv:1904.08819 | |
Prof. karam gouda :: Publications: |
|
| Title: | New Subgraph Isomorphism Algorithms: Vertex versus Path-at-a-time Matching. arXiv preprint arXiv:1904.08819 |
| Authors: | Mosab Hassaan & Karam Gouda |
| Year: | 2019 |
| Keywords: | Not Available |
| 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 | karam gouda_1904.08819.pdf |
| 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. |
