Maximum Percolation Time in Two-Dimensional Bootstrap Percolation

DOI10.1137/130941584zbMath1371.60169arXiv1310.4457OpenAlexW2007804480MaRDI QIDQ3453576

Michał Przykucki, Fabrício Siqueira Benevides

Publication date: 27 November 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.4457

zbMATH Keywords

bootstrappercolationbootstrap percolation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Related Items (27)

The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree ⋮ Complexity of determining the maximum infection time in the geodetic convexity ⋮ The time of bootstrap percolation in two dimensions ⋮ Computational Complexity of Biased Diffusion-Limited Aggregation ⋮ Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box ⋮ Neighborhood growth dynamics on the Hamming plane ⋮ The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results ⋮ Minimum degree conditions for small percolating sets in bootstrap percolation ⋮ On slowly percolating sets of minimal size in bootstrap percolation ⋮ The maximum time of 2-neighbor bootstrap percolation: complexity results ⋮ Long running times for hypergraph bootstrap percolation ⋮ Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three ⋮ On the running time of hypergraph bootstrap percolation ⋮ Target set selection with maximum activation time ⋮ The maximum infection time in the geodesic and monophonic convexities ⋮ The P3 infection time is W[1-hard parameterized by the treewidth] ⋮ Smallest percolating sets in bootstrap percolation on grids ⋮ Burning the plane. Densities of the infinite Cartesian grid ⋮ Line Percolation in Finite Projective Planes ⋮ Inapproximability results related to monophonic convexity ⋮ On the maximum running time in graph bootstrap percolation ⋮ On the parameterized complexity of the geodesic hull number ⋮ Bootstrap Percolation on Degenerate Graphs ⋮ The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results ⋮ Maximal Spanning Time for Neighborhood Growth on the Hamming Plane ⋮ The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects ⋮ Minimal contagious sets in random regular graphs

This page was built for publication: Maximum Percolation Time in Two-Dimensional Bootstrap Percolation