Proceedings of the 2013 International Conference on Advanced Information Engineering and Education Science (ICAIEES 2013)

An Efficient Sub-graph Isomorphism Algorithm Based on Breadth First Strategy

Authors
Weixin Tian
Corresponding Author
Weixin Tian
Available Online December 2013.
DOI
10.2991/icaiees-13.2013.65How to use a DOI?
Keywords
sub-graph isomorphism, BFS, graph matching, vertices pair
Abstract

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.

Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2013 International Conference on Advanced Information Engineering and Education Science (ICAIEES 2013)
Series
Advances in Intelligent Systems Research
Publication Date
December 2013
ISBN
10.2991/icaiees-13.2013.65
ISSN
1951-6851
DOI
10.2991/icaiees-13.2013.65How to use a DOI?
Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - Weixin Tian
PY  - 2013/12
DA  - 2013/12
TI  - An Efficient Sub-graph Isomorphism Algorithm Based on Breadth First Strategy
BT  - Proceedings of the 2013 International Conference on Advanced Information Engineering and Education Science (ICAIEES 2013)
PB  - Atlantis Press
SP  - 242
EP  - 245
SN  - 1951-6851
UR  - https://doi.org/10.2991/icaiees-13.2013.65
DO  - 10.2991/icaiees-13.2013.65
ID  - Tian2013/12
ER  -