A Parallel Subgraph Isomorphism Algorithm on Multi-Core Platform

Abstract:

Subgraph isomorphism is an elemental issue in graph theory. Being the NP-hard problem overall, it is suitable for developing parallel algorithm to reduce the cost time. This paper presented an efficient isomorphism algorithm based on breadth first strategy and a scheme to decompose the matching task over multi-core platforms. The algorithm sorts the vertices of the two graphs by the the degree of outedge and inedge, then adds all the vertices to the feasible pair according to the connection relations of the current vertex. All the tasks distributed among the multi-cores share the same memory. The experiment shows that it has the better performance than current algorithm as the edges increase.

• Periodical: Applied Mechanics and Materials (Volumes 513-517)
• Pages: 483-486
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.513-517.483
• Online since: February 2014
• Authors: Long Yuan, Wei Xin Tian*
• Keywords: Multi-Core Platform, Parallel Algorithm, Subgraph Isomorphism

References

[1] Ullmann, J. R. Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. ACM J. Exp. Algor. 15, (2011).

DOI: 10.1145/1671970.1921702

[2] L. P. Cordella, P. Foggia, C. Sansone and M. Vento, An improved algorithm for matching large graphs, in Proc. 3rd IAPR-TC15 Workshop Graph-Based Represen- tations in Pattern Recognition, 2001, 149-159.

DOI: 10.1109/icpr.1998.712014

[3] Conte,D., Foggia,F., Sansone,C. &Vento,M. Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence 18(3), 2004, 265–298.

DOI: 10.1142/s0218001404003228

[4] Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh B.V. Raghavendra Rao. Faster algorithms for finding and counting subgraphs. Journal of Computer and System Sciences 78 , 2012, 698–706.

DOI: 10.1016/j.jcss.2011.10.001

[5] MohammadTaghi Hajiaghayi, Naomi Nishimura. Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth. Journal of Computer and System Sciences 73, 2007, 755–768.

DOI: 10.1016/j.jcss.2007.01.003

[6] M. M. A. Patwary, R. H. Bisseling, and F. Manne. Parallel greedy graph matching using an edge partitioning approach. In Proceedings of the fourth international workshop on Highlevel parallel programming and applications, HLPP '10, pages 45-54, New York, NY, USA, 2010. ACM.

DOI: 10.1145/1863482.1863493

[7] Todd Plantenga. Inexact subgraph isomorphism in MapReduce. J. Parallel Distrib. Comput. 73, 2013, 164–175.

DOI: 10.1016/j.jpdc.2012.10.005

[8] P. Foggia, C. Sansone and M. Vento, A Database of Graphs for Isomorphism and Sub Graph Isomorphism Benchmarking, Proc. Third IAPR TC-15 Int', l Workshop Graph Based Representations, pp.176-188, (2001).

DOI: 10.1016/s0167-8655(02)00253-2