Asynchronous threshold networks

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

Let G=(V,E) be a graph with an initial sign s(v)∈{±1} for every vertex v∈V. When a certex v becomes active, it resets its sign to s′(v) which is the sign of the majority of its neighbors (s′(v)=1 if there is a tie). G is in a stable state if, s′(v) for all v∈V. We show that for every graph G=(V,E) and every initial signs, there is a sequence v 1, v 2, ...,v r of vertices of G, in which no vertex appears more than once, such that if v i becomes active at time i, (1≤i≤r), then after these r steps G reaches a stable state. This proves a conjecture of Miller. We also consider some generalizations to directed graphs with weighted edges.

Original languageEnglish (US)
Pages (from-to)305-310
Number of pages6
JournalGraphs and Combinatorics
Volume1
Issue number1
DOIs
StatePublished - Dec 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Asynchronous threshold networks'. Together they form a unique fingerprint.

  • Cite this