The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
From MaRDI portal
Publication:2945205
DOI10.1007/978-3-319-12340-0_31zbMath1417.05224OpenAlexW2963865169MaRDI QIDQ2945205
Samuel Nascimento, Thiago Marcilon, Rudini Menezes Sampaio
Publication date: 9 September 2015
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-12340-0_31
Analysis of algorithms and problem complexity (68Q25) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree ⋮ The maximum infection time in the geodesic and monophonic convexities ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ The P3 infection time is W[1-hard parameterized by the treewidth] ⋮ Computing the \(\mathcal{P}_3\)-hull number of a graph, a polyhedral approach ⋮ Inapproximability results related to monophonic convexity ⋮ The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On slowly percolating sets of minimal size in bootstrap percolation
- The time of bootstrap percolation with dense initial sets
- Maximal percolation time in hypercubes under 2-bootstrap percolation
- Irreversible conversion of graphs
- Bootstrap percolation in living neural networks
- Bootstrap percolation on the hypercube
- Bootstrap percolation in three dimensions
- Growth rates and explosions in sandpiles
- Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
- Minimal percolating sets in bootstrap percolation
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Convex sets in graphs. II: Minimal path convexity
- Sharp metastability threshold for two-dimensional bootstrap percolation
- Some remarks on simple tournaments
- Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
- On the Approximability of Influence in Social Networks
- Convexity in Graphs and Hypergraphs
- Random disease on the square grid
- On the Carathéodory Number for the Convexity of Paths of Order Three
- Bootstrap Percolation in High Dimensions
- The sharp threshold for bootstrap percolation in all dimensions
- Some Elementary Properties of Interval Convexities
This page was built for publication: The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
