The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results

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

zbMATH Keywords

\(P_3\)-convexitymaximum time2-neighbour bootstrap percolationinfection on graphs

Mathematics Subject Classification ID

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