| publication name | A fast algorithm for subgraph search problem |
|---|---|
| Authors | Karam Gouda · Mosab Hassaan |
| year | 2012 |
| keywords | |
| journal | (INFOS), 2012 8th International Conference on Informatics and Systems |
| volume | Not Available |
| issue | Not Available |
| pages | DE-53 - DE-59 |
| publisher | IEEE |
| Local/International | International |
| Paper Link | http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6236514 |
| Full paper | download |
| Supplementary materials | Not Available |
Abstract
Graphs are widely used to model complicated data semantics in many applications. In this paper we propose Fast-ON, an efficient algorithm for subgraph isomorphism problem which has proven to be NP-complete. Fast-ON is based on Ullman algorithm [1]. It improves the search space of Ullman algorithm by considering two effective optimizations. Comparing to the well-known algorithms Ullman and Vflib [2], Fast-ON achieves up to 1–3 orders of magnitude speed-up.