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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider a non-monotone activation process $(X_t)_{t\in\{ 0,1,2,\ldots\}}$on a graph $G$, where $X_0\subseteq V(G)$, $X_t=\{ u\in V(G):|N_G(u)\capX_{t-1}|\geq \tau(u)\}$ for every positive integer $t$, and $\tau:V(G)\to\mathbb{Z}$ is a threshold function. The set $X_0$ is a so-called non-monotonetarget set for $(G,\tau)$ if there is some $t_0$ such that $X_t=V(G)$ for every$t\geq t_0$. Ben-Zwi, Hermelin, Lokshtanov, and Newman [Discrete Optimization 8(2011) 87-96] asked whether a target set of minimum order can be determinedefficiently if $G$ is a tree. We answer their question in the affirmative forthreshold functions $\tau$ satisfying $\tau(u)\in \{ 0,1,d_G(u)\}$ for everyvertex~$u$. For such restricted threshold functions, we give a characterizationof target sets that allows to show that the minimum target set problem remainsNP-hard for planar graphs of maximum degree $3$ but is efficiently solvable forgraphs of bounded treewidth.

Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree