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

DOI10.1007/978-3-319-12340-0_31zbMATH Open1417.05224OpenAlexW2963865169MaRDI QIDQ2945205FDOQ2945205

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

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

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)

Cites Work

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

Cited In (12)

• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• Inapproximability results related to monophonic convexity
• Computing the \(\mathcal{P}_3\)-hull number of a graph, a polyhedral approach
• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• Title not available (Why is that?)
• Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness
• The maximum infection time in the geodesic and monophonic convexities
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• The convexity of induced paths of order three and applications: complexity aspects
• The P3 infection time is W[1]-hard parameterized by the treewidth
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results

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)