|
28th Annual Conference on Current
Trends in
Theory and Practice of Informatics
|
|
November 24 - December 1, 2001
|
|
On Majority Voting Games in Trees
by Rastislav Kralovic
Abstract:
We consider a synchronous coloring game played on
a simple connected graph. During one step of the game, each vertex is
recolored according to the majority of its neighbours. This type of synchronous
dynamic systems has been extensively studied and has many applications in
molecular biology, distributed systems modeling, etc. We give the number of
fixpoints of this system on complete binary trees.
An important and well studied structure in this system is the basin of
attraction of a monochromatic fixpoint; its elements are called {\em dynamos}.
We present an algorithm on trees for testing whether a configuration is an
irreversible dynamo.