%0 Journal Article %F ELHIBAOUI-2010-451114 %A El Hibaoui, Abdelaaziz %A Robson, John Michael %A Saheb-Djahromi, Nasser %A Zemmari, Akka %T Uniform Election in Trees and Polyominoids %J Discrete Applied Mathematics %N 158 %P 981-987 %X Election is a classical paradigm in distributed algorithms. This paper aims to design and analyze a distributed algorithm choosing a node in a graph which models a network. In case the graph is a tree, a simple schema of algorithm acts as follows: it removes leaves till the graph is reduced to a single vertex: the elected one. In \cite{MSZ03}, the authors studied a randomized variant of this schema which gives the same probability of being elected to each node of the tree. They conjectured that expected election duration of this algorithm is $O(\ln(n))$ where $n$ denotes the size of the tree and asked whether it is possible to use the same algorithm to obtain a fair election in other classes of graphs. In this paper, we prove their conjecture. We then introduce a new structure called polyominoid graphs. We show how a spanning tree for these graphs can be computed locally so that our algorithm, applied to this spanning tree, gives a uniform election algorithm on polyominoids %U http://hal.archives-ouvertes.fr/hal-00451114 %D 2010