Reducing algorithm for percolation cluster analysis

Abstract

The determination of percolation threshold is the substantial question for a lot of problems which may be modeled by the formalism of cellular automata. There is a set of well known algorithms which deal with this topic. All of them have some advantages and drawbacks connected to calculational or memory complexity. In our work we are going to present a new approach which we call reducing algorithm. In our procedure we avoid the large memory occupancy which is usually connected to the algorithms aiming not only at confirming the existence of percolation cluster. Our approach makes it also possible to reduce time complexity by only single scan through the analyzed space. In the paper we present some basics of algorithm and the comparison of its effectiveness to other, mentioned earlier, ones.