Name
Abstract | ||
|---|---|---|
Given a graph G, a function f:V(G)-Z, and an initial 0/1-vertex-labelling c"1:V(G)-{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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2012.05.042 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
local majority process,initial label,iterative polling process,processes model consensus issue,graph G,dynamic monopoly,efficient algorithm,contributions concern computational aspect,reversible iterative graph process,1-vertex-labelling process,different label | Journal | 460, |
ISSN | Citations | PageRank |
0304-3975 | 4 | 0.57 |
References | Authors | |
27 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitre C. Dourado | 1 | 242 | 18.13 |
| Lucia Draque Penso | 2 | 196 | 20.46 |
| Dieter Rautenbach | 3 | 946 | 138.87 |
| Jayme L. Szwarcfiter | 4 | 546 | 45.97 |