Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Parallel Algorithm for Solving the Graph Isomorphism Problem

Parallel Algorithm for Solving the Graph Isomorphism Problem —In this paper, we propose a parallel algorithm for solving the graph isomorphism problem. Our goal is to construct a suitable vertex substitution or to prove the absence of such. The problem is solved for undirected graphs without loops and multiple edges; it is assumed that the graphs can be disconnected. The question of the existence or absence of an algorithm with a polynomial complexity is currently open. Therefore, as for any time-consuming task, the question arises about speeding up its solution by parallelizing the algorithm. The RPM_ParLib library developed by the author allows developing effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework. Supporting a recursive-parallel programming style, such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. The library can be used for applications written in any programming language supported by the .NET Framework. To solve our problem and conduct a numerical experiment, several applications in the C# language were developed. The purpose of the experiment was to study the acceleration achieved due to the recursive-parallel organization of calculations. Specially generated random regular graphs with various degrees of vertices were used as the initial data. A detailed description of the algorithm and experiment, as well as the results obtained, are also given. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Automatic Control and Computer Sciences Springer Journals

Parallel Algorithm for Solving the Graph Isomorphism Problem

Download PDF
6 pages

Loading next page...
 
/lp/springer-journals/parallel-algorithm-for-solving-the-graph-isomorphism-problem-U1y0EHODmI
Publisher
Springer Journals
Copyright
Copyright © Allerton Press, Inc. 2021. ISSN 0146-4116, Automatic Control and Computer Sciences, 2021, Vol. 55, No. 7, pp. 617–622. © Allerton Press, Inc., 2021. Russian Text © The Author(s), 2020, published in Modelirovanie i Analiz Informatsionnykh Sistem, 2020, No. 1, pp. 86–94.
ISSN
0146-4116
eISSN
1558-108X
DOI
10.3103/s0146411621070166
Publisher site
See Article on Publisher Site

Abstract

—In this paper, we propose a parallel algorithm for solving the graph isomorphism problem. Our goal is to construct a suitable vertex substitution or to prove the absence of such. The problem is solved for undirected graphs without loops and multiple edges; it is assumed that the graphs can be disconnected. The question of the existence or absence of an algorithm with a polynomial complexity is currently open. Therefore, as for any time-consuming task, the question arises about speeding up its solution by parallelizing the algorithm. The RPM_ParLib library developed by the author allows developing effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework. Supporting a recursive-parallel programming style, such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. The library can be used for applications written in any programming language supported by the .NET Framework. To solve our problem and conduct a numerical experiment, several applications in the C# language were developed. The purpose of the experiment was to study the acceleration achieved due to the recursive-parallel organization of calculations. Specially generated random regular graphs with various degrees of vertices were used as the initial data. A detailed description of the algorithm and experiment, as well as the results obtained, are also given.

Journal

Automatic Control and Computer Sciences – Springer Journals

Published: Dec 1, 2021

Keywords: graph isomorphism problem; parallel algorithm; recursion; .NET

References

  • A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices
    Schmidt, D.C.; Druffel, L.E.
  • Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor
    Pogrebnoy, V.K.; Pogrebnoy, A.
  • Polynomiality of method for computing graph structure integral descriptor
    Pogrebnoy, V.K.; Pogrebnoy, A.
  • Complete graph invariant and algorithm of its computation
    Pogrebnoy, A.
  • Method of graph vertices differentiation and solution of the isomorphism problem
    Pogrebnoy, A.; Pogrebnoy, V.K.
  • Method of graph vertices differentiation and solution of the isomorphism problem in geoinformatics
    Pogrebnoy, A.; Pogrebnoy, V.K.
  • Algorithms of comparative analysis of two invariants of a graph, Sovrem. Inf. Tekhnol.
    Melnikov, B.F.; Churikova, N.P.
  • On the recursive-parallel programming for the. NET framework
    Vasilchikov, V.V.
  • On optimization and parallelization of the little algorithm for solving the travelling salesman problem
    Vasilchikov, V.V.
  • On a recursive-parallel algorithm for solving the knapsack problem
    Vasilchikov, V.V.
  • Generating random regular graphs quickly
    Steger, A.; Wormald, N.