Banner

New Subgraph Isomorphism Algorithms: Vertex versus Path-at-a-time Matching. arXiv preprint arXiv:1904.08819

arXiv preprint arXiv:1904.08819 • 2019
Back
Publication Information
Authors Mosab Hassaan & Karam Gouda
Keywords Not Available
Journal arXiv preprint arXiv:1904.08819
Publisher Not Available
Volume Not Available
Issue Not Available
Pages Not Available
publication.type International
Paper Link Not Available
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.