The week's pick
Random Articles
Reseach Article
Parallelization of Graph Isomorphism using OpenMP
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 117 - Number 8 |
| Year of Publication: 2015 |
| Authors: Vijaya Balpande, Anjali Mahajan |
10.5120/20576-2982
|
Vijaya Balpande, Anjali Mahajan . Parallelization of Graph Isomorphism using OpenMP. International Journal of Computer Applications. 117, 8 ( May 2015), 33-41. DOI=10.5120/20576-2982
Abstract
Advancement in computer architecture leads to parallelize the sequential algorithm to exploit the concurrency provided by multiple core on single chip. Sequential programs do not gain performance from multicore. For multicore architectures, OPENMP and MPI are application programming interfaces. They can be used for parallelization of codes. For shared memory architecture OPENMP is used, whereas for distributed memory architecture MPI is used . In this paper, analysis of the performance of parallel algorithm over sequential algorithm is done. In particular, Graph Isomorphism problem based on vertex invariants is considered and parallelized using OpenMP. We demonstrate the performance of Graph Isomorphism using variable size graphs and parallelize it using vertical tiling technique on multicore architecture. Our previous work shows, sequential implementation of modified algorithm based on vertex invariants using Euclidian vector performs better than existing algorithm of Graph Isomorphism based on vertex invariants. To analyze the performance of parallel implementation, we present practical experiments with randomly generated graphs.
References
- Alejandro Duran, Marc Gonzales, and Julita Corbalán. Automatic Thread Distribution for Nested Parallelism in OpenMP. In 19th ACM International Conference on Supercomputing, pages 121–130, Cambridge, MA, USA, June 2005
- The Message Passing Interface (MPI) Standard http://wwwunix. mcs. anl. gov/mpi/ and http://www. mpi-forum. org
- Anne C. Elster and David L. Presberg, "Setting Standards for Parallel Computing: The High Performance FORTRAN and Message Passing Interface Efforts", May 1993, Theory Center SMART NODE Newsletter, Vol. 5, No. 3. http://www. idi. ntnu. no/ elster
- T. Washio and H. Motoda. State of the art of graph-based data mining. ACM SIGKDD Explorations Newsletter, 5(1):59–68,2003
- D. Conte and et al. Graph matching applications in pattern recognition and image processing. In International Conference on Image Processing, volume 2, pages 21–24. IEEE, 2003.
- A. T. Berztiss. A backtrack procedure for isomorphism of directed graphs. Journal of the ACM, 20(3):365–377, 1973.
- J. Braun and et al. Molgen-cid, a canonizer for molecules and graphs accessible through the internet. Journal of Chemical Information and Computer Sciences, 44(2):542–548, 2004.
- Ming Qiu , Haibin Hu, Qingshan Jiang and Hailong Hu : A New Approach of Graph Isomorphism Detection based on Decision Tree IEEE, Second International workshop on Education Technology and Computer Science,2010
- B. T. Messmer and H. Bunke: A decision tree approach to graph and subgraph isomorphism detection Pattern Recognition 32 (1999) 1979-1998
- B. T. Messmer and H. Bunke: Subgraph Isomorphism in Polynomial Time. University of Bern, Institute of Computer Science and Applied Mathematics, Bern, Switzerland Technical Report IAM 1995-003, 1995
- Narsingh Deo: Graph Theory with Applications to Engineering and Computer Science ,Prentice Hall,Inc, 1995
Index Terms
Keywords