Complementary algorithms for graphs and percolation

Abstract

A pair of complementary algorithms are presented. One of the pair is a fast method for connecting graphs with an edge. The other is a fast method for removing edges from a graph. Both algorithms employ the same tree based graph representation and so, in concert, can arbitrarily modify any graph. Since the clusters of a percolation model may be described as simple connected graphs, an efficient Monte Carlo scheme can be constructed that uses the algorithms to sweep the occupation probability back and forth between two turning points. This approach concentrates computational sampling time within a region of interest. A high precision value of pc = 0.59274603(9) was thus obtained, by Mersenne twister, for the two dimensional square site percolation threshold.

5 pages, 3 figures, poster version presented at statphys23 (2007)

References in corpus (6)

• A fast Monte Carlo algorithm for site or bond percolation
• Efficient Monte Carlo algorithm and high-precision results for percolation
• Invaded cluster algorithm for Potts models
• Invaded cluster algorithm for equilibrium critical points
• Convergence of threshold estimates for two-dimensional percolation
• Probability-Changing Cluster Algorithm for Potts Models

Cited by in corpus (8)

• Pseudorandom Number Generators and the Square Site Percolation Threshold
• Nonmonotonic size dependence of the critical concentration in 2D percolation of straight rigid rods under equilibrium conditions
• Conformal invariance in three dimensional percolation
• Berezinskii-Kosterlitz-Thouless-like percolation transitions in the two-dimensional XY model
• Exact Percolation Probability on the Square Lattice
• On the metric distortion of nearest-neighbour graphs on random point sets
• Sparse power-efficient topologies for wireless ad hoc sensor networks
• Errata and Addenda to Mathematical Constants