The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results

DOI10.1007/978-3-662-53174-7_13zbMath1417.05225arXiv1508.06847OpenAlexW1906048684MaRDI QIDQ2827810

Thiago Marcilon, Rudini Menezes Sampaio

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

treewidthfixed parameter tractabilitygrid graph2-neighbor bootstrap percolationmaximum percolation time

Mathematics Subject Classification ID

Epidemiology (92D30) 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 (1)

The P3 infection time is W[1-hard parameterized by the treewidth]

Cites Work

• 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
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• Bootstrap percolation in living neural networks
• A simplified NP-complete satisfiability problem
• 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
• On the structure of graphs with few \(P_4\)s
• Sharp metastability threshold for two-dimensional bootstrap percolation
• The convexity of induced paths of order three and applications: complexity aspects
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• Inapproximability Results for Graph Convexity Parameters
• On two geometric problems related to the travelling salesman problem
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On the Approximability of Influence in Social Networks
• Random disease on the square grid
• Hamilton Paths in Grid Graphs
• Bootstrap Percolation in High Dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Efficient algorithms for graphs with few \(P_4\)'s

This page was built for publication: The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results