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

DOI10.1007/978-3-319-12340-0_31MaRDI QIDQ2945205zbMATH OpenOpenAlexFDO

Authors Thiago Marcilon, Samuel Nascimento, Rudini M. 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

Graph algorithms (graph-theoretic aspects) (05C85) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The maximum time of 2-neighbor bootstrap percolation: complexity results
• scientific article; zbMATH DE number 6302977
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• The time of bootstrap percolation in two dimensions
• The complexity of the bootstraping percolation and other problems
• On the maximum running time in graph bootstrap percolation
• The time of graph bootstrap percolation

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 6302977 (Why is no real title available?)
• scientific article; zbMATH DE number 3068278 (Why is no real title available?)
• Bootstrap percolation in high dimensions
• Bootstrap percolation in living neural networks
• Bootstrap percolation in three dimensions
• Bootstrap percolation on the hypercube
• Convex sets in graphs. II: Minimal path convexity
• Convexity in Graphs and Hypergraphs
• Growth rates and explosions in sandpiles
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• Minimal percolating sets in bootstrap percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• On the Carathéodory number for the convexity of paths of order three
• On the approximability of influence in social networks
• Random disease on the square grid
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Some Elementary Properties of Interval Convexities
• Some remarks on simple tournaments
• The sharp threshold for bootstrap percolation in all dimensions
• The time of bootstrap percolation with dense initial sets

Cited in

(12)

• Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• 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
• Computing the \(\mathcal{P}_3\)-hull number of a graph, a polyhedral approach
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• scientific article; zbMATH DE number 6302977 (Why is no real title available?)
• The convexity of induced paths of order three and applications: complexity aspects
• The P3 infection time is W[1]-hard parameterized by the treewidth
• Inapproximability results related to monophonic convexity

This page was built for publication: The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945205)