Locally Derivable Graphs

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

Abstrakty

EN

In the paper a class of locally derivable graphs is defined and discussed. Well known particular cases of derivable graphs are (among others) trees, complete, and triangular graphs; in the paper a broader class of locally derivable graphs, called closed graphs, is defined. Nodes and edges of closed graphs can be partitioned into external and internal ones; the main property of such graphs their local reducibility: successive removing its external nodes leads eventually to a singleton, and removing its external edges leads to an a spanning tree of the graph. The class of closed graphs is then a class enabling structural reducing. This property can be applied in processor networks to design some local procedures leading to global results.

Słowa kluczowe

EN

graphs; graph transformation; local computations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 75, nr 1-4
• Strony: 335--355
• Opis fizyczny: bibliogr. 11 poz., rys.

Twórcy

autor

Mazurkiewicz A.

• Institute of Computer Science of PAS, Ordona 21,01-237 Warszawa, Pland,

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] Courcelle,B., Métivier,Y.: Coverings and Minors: application to local computations in graphs, in: Europ. Journal of Combinatorics 15 (1994) 127-138
• [4] Dijkstra,E.W.: Solution of a problem in concurrent programming control, Comm. of ACM 8 (1965) 569
• [5] Fisher,M.J., Lynch,N.A., Merritt,A.: Easy impossibility proofs for distributed consensus problems, in: Distributed Computing 1 (1986) 26-29
• [6] 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
• [7] Godard,E., Métivier,Y., MuscholL, A.: The power of local computations in graphs with initial knowledge, in: Proc. of Theory and Applications of Graph Transformations'98 1764 LNCS (2000) 71-84
• [8] Le Lann,G.: Distributed systems - towards a formal approach, in: Information Processing 77 (IFIP), Gilchrist B., (editor), North-Holland (Amsterdam), (1977) 155-160.
• [9] 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
• [10] Litovsky,I., Métivier,Y., Zielonka,W.: On the recognition of families of graphs with local computations, in: Information & Computation 118 (1995) 110-119
• [11] Mazurkiewicz,A.: Local properties of triangular graphs, in: Proc. of CS&P'2006, vol.III, G. Lindemann V.Trzebiatowski, H.Schlingloff, eds. (2006) 400-409