COMPARISON OF GRASSBERGER AND AKHUNZHANOV ALGORITHMS FOR FINDING THE BACKBONE OF PERCOLATION CLUSTER IN PROBLEMS OF SITE PERCOLATION ON SQUARE LATTICE
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.