Name
Abstract | ||
|---|---|---|
In this paper we extend the setting of irreversible dynamic monopolies (or shortly, dynamos) from two to more than two colors. The distributed protocol can be described as follows: let G be a simple connected graph where every node has a color from a finite ordered set C = { 1 , ¿ , k } of colors. At each round, each node can increase its color by 1 according to the colors held by its neighbors. We are interested in the so called SCIM-dynamos, that is, subsets of nodes initially having color k leading all the nodes to recolor by k under our protocol. We show that there is a tradeoff between the size of a SCIM-dynamo and the size of C : if C is limited to two colors, our protocol coincides with the irreversible strong majority. Differently, increasing the number of colors employed permits to reduce the size of a SCIM-dynamo to that of a minimum simple majority dynamo. This gives rise to an inclusion hierarchy of dynamos from simple majority dynamos to strong majority dynamos. Our goal is to minimize the size of a SCIM-dynamo for a given G, and then to determine the minimum number of colors accordingly. In particular, given an m × n torus, we show that there exists a special class of minimum size SCIM-dynamos for k ¿ min ( m , n ) / 2 . |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.tcs.2015.06.035 | Theor. Comput. Sci. |
Keywords | Field | DocType |
Distributed algorithms,Irreversible dynamic monopolies,Target set selection | Dynamo,Ordered set,Discrete mathematics,Combinatorics,Existential quantification,Torus,Distributed algorithm,Connectivity,Hierarchy,Mathematics | Journal |
Volume | Issue | ISSN |
596 | C | 0304-3975 |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sara Brunetti | 1 | 122 | 16.23 |
| Elena Lodi | 2 | 154 | 16.21 |
| Walter Quattrociocchi | 3 | 19 | 4.88 |