CASPIAN JOURNAL
MANAGEMENT AND HIGH TECHNOLOGIES
COMPARISON OF GRASSBERGER AND AKHUNZHANOV ALGORITHMS FOR FINDING THE BACKBONE OF PERCOLATION CLUSTER IN PROBLEMS OF SITE PERCOLATION ON SQUARE LATTICE
 |
Read | Gordeev Ivan I., Saenko Natalya S. COMPARISON OF GRASSBERGER AND AKHUNZHANOV ALGORITHMS FOR FINDING THE BACKBONE OF PERCOLATION CLUSTER IN PROBLEMS OF SITE PERCOLATION ON SQUARE LATTICE // Caspian journal : management and high technologies. — 2022. — №3. — pp. 44-60. |
Gordeev Ivan I. - Astrakhan State University named after V. N. Tatishchev
Saenko Natalya S. - Astrakhan State University named after V. N. Tatishchev
This article compares the Grassberger algorithm and the Akhunzhanov algorithm for finding the conducting backbone of percolation cluster. Since the Grassberger algorithm was proposed for the problems of site percolation on square lattice, the comparison of algorithms is made in these problems. For the Grassberger algorithm, we discuss in detail the cases when the algorithm incorrectly attaches dangling parts to the backbone. We discuss also modifications of the Grassberger algorithm, which allow to reduce the number of dangling parts attached to the backbone. Then Akhunzhanov`s algorithm, which allows separating all dangling parts from the backbone, is discussed. An estimate is given of the proportion of sites incorrectly attached to the backbone by different versions of the Grassberger algorithm. A theoretical estimate of the time complexity of the Akhunzhanov algorithm and an experimental comparison of the runtime of different versions of the Grassberger algorithm and the Akhunzhanov algorithm are also given.
Key words: backbone identification, site percolation, two-dimensional lattice, open boundary conditions, graph algorithms, Grassberger algorithm, Akhunzhanov algorithm