Local Properties of Triangular Graphs

• Autorzy: Mazurkiewicz A.
• Języki publikacji: EN

Abstrakty

EN

In the paper triangular graphs are discussed. The class of triangular graphs is of special interest as unifying basic features of complete graphs and trees. The main issue addressed in the paper is to characterize class of triangular graphs (defined globally) by local means. Namely, it is proved that any triangular graph can be constructed from a singleton by successive extensions with nodes having complete neighborhoods. Next, the proved theoretical properties are applied for designing some local algorithms for triangular graphs: for elections a leader and for constructing their spanning trees. The fairness of these algorithms is proved, which means that any node can be elected and any spanning tree can be constructed by execution of these algorithms.

Słowa kluczowe

EN

triangular graphs; local computations; leader election; spanning tree

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 3-4
• Strony: 487--495
• Opis fizyczny: bibliogr. 6 poz.

Twórcy

autor

Mazurkiewicz A.

• Institute of Computer Science, Polish Academy of Science, Ordona 21, 01-237 Warsaw, Poland,

Bibliografia

• [1] Angluin,D.: Local and global properties in networks of processors, in: Proc. of 12th Symp. on Theory of Computing (1980) 82-93
• [2] Berge, C.: Theorie des graphes et ses applications, Dunod, Paris (1958)
• [3] Godard,E.:(Ph.D. dissertation) A characterization of families of graphs in which election is possible, in: Proc. of Foundations of Software Sci. and Comp. Structures, LNCS 2303 (2002) 159-171
• [4] Le Lann,G.: Distributed systems - towards a formal approach, in: Information Processing 77 (IFIP), Gilchrist B., (editor), North-Holland (Amsterdam), (1977) 155-160.
• [5] Litovsky,I., Métivier,Y., Sopena,E.: Graph relabelling systems and distributed algorithms, in: H.Ehrig, H.-J.Kreowski, U.Montanari, and G.Rozenberg (eds) Handbook of graph grammars and computing by graph transformation 3, World Scientific (1999) 1- 56
• [6] Zielonka,W.: Traces and Automata, lecture delivered at Bordeaux University, September 2005