Abstract of Paper

Randomized algorithms for determining the majority on graphs
by Gianluca De Marco, Andrzej Pelc


Every node of an undirected connected graph is colored 
white or black. Adjacent nodes can be compared
and the outcome of each comparison is either 0 
(same color) or 1 (different colors).
The aim is to discover a node of the majority color, 
or to conclude that there is the same 
number of black and white nodes. We consider randomized 
algorithms for this task and establish
upper and lower bounds on their expected running time. 
Our main contribution are lower bounds
showing that some simple and natural algorithms for 
this problem cannot be improved in general.