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.
أعضاء هيئة التدريس - جامعة بنها