CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Parallelization of Graph Isomorphism using OpenMP

by Vijaya Balpande, Anjali Mahajan
journal cover thumbnail

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

@article{ 10.5120/20576-2982,
author = { Vijaya Balpande, Anjali Mahajan },
title = { Parallelization of Graph Isomorphism using OpenMP },
journal = { International Journal of Computer Applications },
issue_date = { May 2015 },
volume = { 117 },
number = { 8 },
month = { May },
year = { 2015 },
issn = { 0975-8887 },
pages = { 33-41 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume117/number8/20576-2982/ },
doi = { 10.5120/20576-2982 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:58:50.083086+05:30
%A Vijaya Balpande
%A Anjali Mahajan
%T Parallelization of Graph Isomorphism using OpenMP
%J International Journal of Computer Applications
%@ 0975-8887
%V 117
%N 8
%P 33-41
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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
  2. The Message Passing Interface (MPI) Standard http://wwwunix. mcs. anl. gov/mpi/ and http://www. mpi-forum. org
  3. 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
  4. T. Washio and H. Motoda. State of the art of graph-based data mining. ACM SIGKDD Explorations Newsletter, 5(1):59–68,2003
  5. 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.
  6. A. T. Berztiss. A backtrack procedure for isomorphism of directed graphs. Journal of the ACM, 20(3):365–377, 1973.
  7. 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.
  8. 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
  9. B. T. Messmer and H. Bunke: A decision tree approach to graph and subgraph isomorphism detection Pattern Recognition 32 (1999) 1979-1998
  10. 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
  11. Narsingh Deo: Graph Theory with Applications to Engineering and Computer Science ,Prentice Hall,Inc, 1995
Index Terms

Computer Science
Information Sciences

Keywords

Graph Isomorphism Vertex Invariant Euclidean vector OpenMP MPI.

Powered by PhDFocusTM