id: 06110696
dt: j
an: 06110696
au: Dourado, Mitre C.; Penso, Lucia Draque; Rautenbach, Dieter; Szwarcfiter,
    Jayme L.
ti: Reversible iterative graph processes.
so: Theor. Comput. Sci. 460, 16-25 (2012).
py: 2012
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: conquest and expansion games; local majority process; iterative polling
    process; consensus; dynamic monopoly; reachability problems; finite
    discrete dynamical systems; local interaction games
ci: 
li: doi:10.1016/j.tcs.2012.05.042
ab: Summary: Given a graph $G$, a function $f:V(G)\to {\Bbb{Z}}$, and an
    initial 0/1-vertex-labelling $c_{1}:V(G)\to \{0,1\}$, we study an
    iterative 0/1-vertex-labelling process on $G$ where in each round every
    vertex $v$ changes its label if and only if at least $f(v)$ neighbours
    have a different label. For special choices of the values of $f$, such
    processes model consensus issues and have been studied under names such
    as local majority processes or iterative polling processes in a large
    variety of contexts especially in distributed computing. Our
    contributions concern computational aspects related to the minimum
    cardinality $r_{f}(G)$ of sets of vertices with initial label 1 such
    that during the process on G all vertices eventually change their label
    to 1. Such sets are known as dynamic monopolies or dynamos for short.
    We establish a hardness result and describe efficient algorithms for
    restricted instances on paths and cycles.
rv: