Local Computations in Graphs: The Case of Cellular Edge Local Computations

Issue title: SPECIAL ISSUE ON ICGT 2004

Article type: Research Article

Authors: Chalopin, Jérémie | Métivier, Yves | Zielonka, Wiesław

Affiliations: LaBRI ENSEIRB, Université Bordeaux 1 351 cours de la Libération, 33405 Talence, France. E-mail: {chalopin,metivier}@labri.fr | LIAFA Université Paris 7 2 place Jussieu, Case 7014, 75251 Paris Cedex 05, France. E-mail: zielonka@liafa.jussieu.fr

Abstract: We examine the power and limitations of the weakest vertex relabelling system which allows to change a label of a vertex in function of its own label and of the label of one of its neighbours. We characterize the graphs for which two important distributed algorithmic problems are solvable in this model: naming and election.

Keywords: Distributed Computing, Local Computations, Election, Naming, Submersion

Journal: Fundamenta Informaticae, vol. 74, no. 1, pp. 85-114, 2006