Asynchronous threshold networks |
| |
Authors: | Noga Alon |
| |
Institution: | (1) Department of Mathematics, Tel Aviv University, Tel Aviv, Israel;(2) Bell Communications Research, 07960 Morristown, NJ, USA |
| |
Abstract: | LetG=(V,E) be a graph with an initial signs(v)∈{±1} for every vertexv∈V. When a certexv becomesactive, it resets its sign tos′(v) which is the sign of the majority of its neighbors(s′(v)=1 if there is a tie).G is in astable state if,s′(v) for allv∈V. We show that for every graphG=(V,E) and every initial signs, there is a sequencev
1,v
2,...,v
r
of vertices ofG, in which no vertex appears more than once, such that ifv
i
becomes active at timei, (1≤i≤r), then after theser stepsG reaches a stable state. This proves a conjecture of Miller. We also consider some generalizations to directed graphs with
weighted edges. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|