Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness
From MaRDI portal
Publication:5854892
DOI10.1137/19M1239933zbMath1462.68070arXiv1809.01525OpenAlexW2914817568MaRDI QIDQ5854892
Ivailo Hartarsky, Tamás Róbert Mezei
Publication date: 12 March 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1809.01525
Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Cellular automata (computational aspects) (68Q80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- First passage times for threshold growth dynamics on \(\mathbb{Z}^ 2\)
- The sharp threshold for the Duarte model
- Slow convergence in bootstrap percolation
- Sharp metastability threshold for two-dimensional bootstrap percolation
- Higher order corrections for anisotropic bootstrap percolation
- Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
- Universality for critical KCM: infinite number of stable directions
- Bootstrap percolation, and other automata
- Subcritical $\mathcal {U}$-bootstrap percolation models have non-trivial phase transitions
- Metastability effects in bootstrap percolation
- Reducibility among Combinatorial Problems
- The second term for two-neighbour bootstrap percolation in two dimensions
- Monotone Cellular Automata in a Random Environment
This page was built for publication: Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness