Banner

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

arXiv preprint arXiv:1904.08819 • 2019
العودة
معلومات البحث
المؤلفون Mosab Hassaan & Karam Gouda
الكلمات المفتاحية Not Available
المجلة العلمية arXiv preprint arXiv:1904.08819
الناشر Not Available
المجلد Not Available
العدد Not Available
الصفحات Not Available
publication.type International
رابط البحث Not Available
المواد المرفقة Not Available
الملخص
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.