Characterization of families of graphs in which election is possible


To appear at Foundations of Software Science and Computation Structures (FOSSACS02), Grenoble, France, 6-14 April, 2002


An election algorithm for a network is a procedure that enables to distinguish exactly one vertex of the network. This paper presents a necessary and sufficient condition for a family of graphs to admit an election algorithm. We also give a universal algorithm to proceed an election in a given family where the condition is fulfilled. The condition involves graphs covering and quasi-covering; the universal election algorithm is based upon an enumeration algorithm of Mazurkiewicz and a stable properties detection algorithm of Szymanski, Shi and Prywes.

Server START Conference Manager
Update Time 14 Dec 2001 at 14:02:38
Start Conference Manager
Conference Systems