English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In 2-neighborhood bootstrap percolation on a graph $G$, an infection spreadsaccording to the following deterministic rule: infected vertices of $G$ remaininfected forever and in consecutive rounds healthy vertices with at least twoalready infected neighbors become infected. Percolation occurs if eventuallyevery vertex is infected. The maximum time $t(G)$ is the maximum number ofrounds needed to eventually infect the entire vertex set. In 2013, it wasproved by Benevides et al \cite{eurocomb13} that $t(G)$ is NP-hard for planargraphs and that deciding whether $t(G)\geq k$ is polynomial time solvable for$k\leq 2$, but is NP-complete for $k\geq 4$. They left two open problems aboutthe complexity for $k=3$ and for planar bipartite graphs. In 2014, we solvedthe first problem\cite{wg2014}. In this paper, we solve the second one byproving that $t(G)$ is NP-complete even in grid graphs with maximum degree 3.We also prove that $t(G)$ is polynomial time solvable for solid grid graphswith maximum degree 3. Moreover, we prove that the percolation time problem isW[1]-hard on the treewidth of the graph, but it is fixed parameter tractablewith parameters treewidth$+k$ and maxdegree$+k$.

The maximum time of 2-neighbour bootstrap percolation in grid graphs and some parameterized results