An Efficient Sub-graph Isomorphism Algorithm Based on Breadth First Strategy
Weixin Tian · Advances in intelligent systems research/Advances in Intelligent Systems Research · 2013
Sub-graph isomorphism is an important elemental issue in graph theory.This paper aimed to cope with the fall in performance that the current algorithms meet when the edges of the source graph grow up, and proposed an algorithm based on breadth first strategy.The algorithm sorts the vertices of the two graphs by the degree of out-edge and in-edge and adds all the vertices to the feasible pair according to the connection relations of the current vertex.The onging solution will be discarded and turn to next when any conflicts occur.The experiment shows that it has the better performance than current algorithm when the edges increase.