1996/09/30 by K.J.M. Moriarty, K. Moriarty, Jonathan Machta +3 · 11 citations
Economics, Econometrics and Finance · Mathematics · Physics and Astronomy · #Algorithm #Combinatorics #Complex Network Analysis Techniques #Complex Systems and Time Series Analysis #Computation #Computer science #Diffusion #Dimension (graph theory) #Discrete mathematics #Exponent #Fractal #Fractal dimension #Geometry #Mathematical analysis #Mathematics #Parallel algorithm #Physics #Scaling #Theoretical and Computational Physics #Time complexity #comp-gas #cond-mat.stat-mech #nlin.CG
paper · pdf · doi:10.1103/physreve.55.6211
published in Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics 55(5), 6211-6218 (American Physical Society) · 24 pages Revtex and 2 figures. A major improvement to the algorithm and smaller dynamic exponent in this version
arxiv created 1996/12/17 · openalex publication_date 1997/05/01 · arxiv updated 2016/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
A parallel algorithm for diffusion-limited aggregation (DLA) is described and analyzed from the perspective of computational complexity. The dynamic exponent z of the algorithm is defined with respect to the probabilistic parallel random-access machine model of parallel computation according to T\ensuremath∼Lz, where L is the cluster size, T is the running time, and the algorithm uses a number of processors polynomial in L. It is argued that z=D-D2/2, where D is the fractal dimension and D2 is the second generalized dimension. Simulations of DLA are carried out to measure D2 and to test scaling assumptions employed in the complexity analysis of the parallel algorithm. It is plausible that the parallel algorithm attains the minimum possible value of the dynamic exponent in which case z characterizes the intrinsic history dependence of DLA.