New Subgraph Isomorphism Algorithms: Vertex versus Path-at-a-time Matching. arXiv preprint arXiv:1904.08819
arXiv preprint arXiv:1904.08819 • 2019
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.
Staff Members - Benha University