[PDF][PDF] On the spread of information through graphs
AN Zehmakan - 2019 - research-collection.ethz.ch
Consider a graph G and an initial configuration, where each node is black or white. Assume
that in discrete-time rounds, all nodes simultaneously update their color based on a …
that in discrete-time rounds, all nodes simultaneously update their color based on a …
Counting Problems in Trees, with Applications to Fixed Points of Cellular Automata
V Turau - arxiv preprint arxiv:2312.13769, 2023 - arxiv.org
Cellular automata are synchronous discrete dynamical systems used to describe complex
dynamic behaviors. The dynamic is based on local interactions between the components …
dynamic behaviors. The dynamic is based on local interactions between the components …
Fixed points and 2-cycles of synchronous dynamic coloring processes on trees
V Turau - International Colloquium on Structural Information and …, 2022 - Springer
This paper considers synchronous discrete-time dynamical systems on graphs based on the
threshold model. It is well known that after a finite number of rounds these systems either …
threshold model. It is well known that after a finite number of rounds these systems either …
The structure of configurations in one-dimensional majority cellular automata: from cell stability to configuration periodicity
Y Nakar, D Ron - International Conference on Cellular Automata for …, 2022 - Springer
We study the dynamics of (synchronous) one-dimensional cellular automata with cyclical
boundary conditions that evolve according to the majority rule with radius r. We introduce a …
boundary conditions that evolve according to the majority rule with radius r. We introduce a …
Counting Fixed Points and Pure 2-Cycles of Tree Cellular Automata
V Turau - Latin American Symposium on Theoretical Informatics, 2024 - Springer
Cellular automata are synchronous discrete dynamical systems used to describe complex
dynamic behaviors. The dynamic is based on local interactions between the components …
dynamic behaviors. The dynamic is based on local interactions between the components …
Stabilization Bounds for Influence Propagation from a Random Initial State
PA Papp, R Wattenhofer - arxiv preprint arxiv:2107.02076, 2021 - arxiv.org
We study the stabilization time of two common types of influence propagation. In majority
processes, nodes in a graph want to switch to the most frequent state in their neighborhood …
processes, nodes in a graph want to switch to the most frequent state in their neighborhood …
A General Stabilization Bound for Influence Propagation in Graphs
PA Papp, R Wattenhofer - arxiv preprint arxiv:2004.09185, 2020 - arxiv.org
We study the stabilization time of a wide class of processes on graphs, in which each node
can only switch its state if it is motivated to do so by at least a $\frac {1+\lambda}{2} $ fraction …
can only switch its state if it is motivated to do so by at least a $\frac {1+\lambda}{2} $ fraction …