pith. sign in

arxiv: 1802.03935 · v1 · pith:AHITUYKFnew · submitted 2018-02-12 · 💻 cs.DM · math.CO

Dynamic monopolies for interval graphs with bounded thresholds

classification 💻 cs.DM math.CO
keywords dynamicgraphsthresholdboundedfunctionsintervalmonopolyvertex
0
0 comments X
read the original abstract

For a graph $G$ and an integer-valued threshold function $\tau$ on its vertex set, a dynamic monopoly is a set of vertices of $G$ such that iteratively adding to it vertices $u$ of $G$ that have at least $\tau(u)$ neighbors in it eventually yields the vertex set of $G$. We show that the problem of finding a dynamic monopoly of minimum order can be solved in polynomial time for interval graphs with bounded threshold functions, but is NP-hard for chordal graphs allowing unbounded threshold functions.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.