Treffer: Design and Development of Parallel Algorithm for Graph Isomorphism

A fundamental issue in mathematics and computer science, the problem of graph isomorphism (GI) has applications in many fields, including chemistry, network analysis, and cryptography. To perform GI, two provided graphs must be examined to see if they are isomorphic, which means they share the same basic structure despite any differences in vertex and edge names. Computational complexity theory has long sought to create effective GI algorithms. Due to the increased accessibility of high-performance parallel computing platforms, there has been an increase in interest in parallel methods for GI in recent years. In order to speed up graph isomorphism testing, parallel methods are created to take advantage of multi-core computers, GPUs, and distributed computing clusters. The goal of this research is to create a parallel GI method that takes advantage of parallel processing to speed up computations for extensive graph comparisons. The algorithm uses a divide-and-conquer tactic, breaking down the input graphs into smaller sub-graphs that are then independently examined for isomorphism. The efficiency of these sub-graph comparisons is greatly increased by running them concurrently across numerous processing units. Load balancing algorithms are incorporated into the algorithm to provide scalability, dividing the workload equally among processing units and reducing communication cost. In order to further improve performance, the algorithm also uses optimisation techniques like graph pruning and canonization. The algorithm's success in lowering the temporal complexity of GI for big graphs is demonstrated by experimental data. This research advances graph isomorphism algorithms by utilising parallelism, which has implications for effectively resolving practical issues and overcoming computational difficulties in a variety of scientific and industrial applications.