DocumentCode
564810
Title
A fast algorithm for subgraph search problem
Author
Gouda, K. ; Hassaan, M.
Author_Institution
Fac. of Comput. & Inf., Benha Univ., Benha, Egypt
fYear
2012
fDate
14-16 May 2012
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.
Keywords
graph theory; optimisation; search problems; Fast-ON; NP-complete problem; Ullman algorithm; data semantics; fast algorithm; subgraph isomorphism problem; subgraph search problem; Algorithm design and analysis; Computers; Data engineering; Databases; Educational institutions; Informatics; Optimization;
fLanguage
English
Publisher
ieee
Conference_Titel
Informatics and Systems (INFOS), 2012 8th International Conference on
Conference_Location
Cairo
Print_ISBN
978-1-4673-0828-1
Type
conf
Filename
6236514
Link To Document