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
Reseach Article

Graph Isomorphism Algorithm using Pieces Patching Puzzle Technique (ppp - Technique)

by Mohammad Alhashmi, Abdulaziz Alroomi
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 176 - Number 12
Year of Publication: 2020
Authors: Mohammad Alhashmi, Abdulaziz Alroomi

Mohammad Alhashmi, Abdulaziz Alroomi . Graph Isomorphism Algorithm using Pieces Patching Puzzle Technique (ppp - Technique). International Journal of Computer Applications. 176, 12 ( Apr 2020), 1-7. DOI=10.5120/ijca2020920044

@article{ 10.5120/ijca2020920044,
author = { Mohammad Alhashmi, Abdulaziz Alroomi },
title = { Graph Isomorphism Algorithm using Pieces Patching Puzzle Technique (ppp - Technique) },
journal = { International Journal of Computer Applications },
issue_date = { Apr 2020 },
volume = { 176 },
number = { 12 },
month = { Apr },
year = { 2020 },
issn = { 0975-8887 },
pages = { 1-7 },
numpages = {9},
url = { },
doi = { 10.5120/ijca2020920044 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
%0 Journal Article
%1 2024-02-07T00:42:17.348935+05:30
%A Mohammad Alhashmi
%A Abdulaziz Alroomi
%T Graph Isomorphism Algorithm using Pieces Patching Puzzle Technique (ppp - Technique)
%J International Journal of Computer Applications
%@ 0975-8887
%V 176
%N 12
%P 1-7
%D 2020
%I Foundation of Computer Science (FCS), NY, USA

This paper proposes a novel technique for a polynomial time algorithm to detect an existence of isomorphism between two unlabeled graphs that is fast and accurate for the mass majority of large random graphs. This technique, namely ppp-Technique, is based on cutting the first graph into large sub-graphs to mimic the pieces ( or patches ) of a puzzle that have to be patched to their correct places (or matches ) on the second graph. It is a difficult process to draw the borders of each patch for best results. In other words, deciding the sizes of the patches is an optimization problem. Clearly, the larger these patches are, the faster the algorithm can decide whether an isomorphism exists. The greedy concept has been applied in the process of creating patches which led to high efficiency. The time complexity of the proposed algorithm is O(n3 log n) . Examples that clarify the process of constructing the patches from one graph and matching them to the places in the other one are shown. The algorithm is tested with many graphs with different sizes of nodes and different densities of connecting edges which gave complete accurate results.

  1. M. Zaslavskiy, F. Bach, and J.-P. Vert, “A path following algorithm for the graph matching problem,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 12, pp. 2227–2242, 2008.
  2. K. Liu, Y. Zhang, K. Lu, X. Wang, X. Wang, and G. Tian, “Mapeff: An effective graph isomorphism agorithm based on the discrete-time quantum walk,” Entropy, vol. 21, no. 6, p. 569, 2019.
  3. D. Conte, P. Foggia, C. Sansone, and M. Vento, “Thirty years of graph matching in pattern recognition,” International journal of pattern recognition and artificial intelligence, vol. 18, no. 03, pp. 265–298, 2004.
  4. A. Dawar and K. Khan, “Constructing hard examples for graph isomorphism,” arXiv preprint arXiv:1809.08154, 2018.
  5. L. Babai, A. Dawar, P. Schweitzer, and J. Tor´an, “The graph isomorphism problem (dagstuhl seminar 15511),” in Dagstuhl Reports, vol. 5, no. 12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
  6. G. L. Miller, “Graph isomorphism, general remarks,” Journal of Computer and System Sciences, vol. 18, no. 2, pp. 128–142, 1979.
  7. B. D. McKay and A. Piperno, “Practical graph isomorphism, ii,” Journal of Symbolic Computation, vol. 60, pp. 94–112, 2014.
  8. G. Nikolentzos, P. Meladianos, and M. Vazirgiannis, “Matching node embeddings for graph similarity,” in Thirty-First AAAI Conference on Artificial Intelligence, 2017.
  9. V. Bonnici, R. Giugno, A. Pulvirenti, D. Shasha, and A. Ferro, “A subgraph isomorphism algorithm and its application to biochemical data,” BMC bioinformatics, vol. 14, no. S7, p. S13, 2013.
  10. S. B. Akers, “The star graph: An attractive alternative to the n-cube,” in Proc. Int’l Conf. Parallel Processing., 1987, 1987.
  11. M. Verma and S. Sharma, “A greedy approach for coverage hole detection and restoration in wireless sensor networks,” Wireless Personal Communications, vol. 101, no. 1, pp. 75– 86, 2018.
  12. H. Joudrier and F. Thiard, “A greedy approach for a rolling stock management problem using multi-interval constraint propagation,” Annals of Operations Research, vol. 271, no. 2, pp. 1165–1183, 2018.
  13. Y. Duan, J. Wu, and H. Zheng, “A greedy approach for carpool scheduling optimisation in smart cities,” International Journal of Parallel, Emergent and Distributed Systems, pp. 1–15, 2018.
  14. E. Oh and C. Woo, “Performance analysis of dynamic channel allocation based on the greedy approach for orthogonal frequency-division multiple access downlink systems,” International Journal of Communication Systems, vol. 25, no. 7, pp. 953–961, 2012.
  15. N. Meghanathan, “A greedy algorithm for neighborhood overlap-based community detection,” Algorithms, vol. 9, no. 1, p. 8, 2016.
  16. L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “An improved algorithm for matching large graphs,” in 3rd IAPRTC15 workshop on graph-based representations in pattern recognition, 2001, pp. 149–159.
  17. C. McCreesh, P. Prosser, C. Solnon, and J. Trimble, “When subgraph isomorphism is really hard, and why this matters for graph databases,” Journal of Artificial Intelligence Research, vol. 61, pp. 723–759, 2018.
Index Terms

Computer Science
Information Sciences


Unlabeled Graphs Random Graphs Graph Matching Isomorphism