Wyniki wyszukiwania - BazTech

Ograniczanie wyników

4 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: local computations

Sortuj według:

Ogranicz wyniki do:

Locally Derivable Graphs

Mazurkiewicz A.

Fundamenta Informaticae

2007

Vol. 75, nr 1-4

335-355

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.

Local Properties of Triangular Graphs

Mazurkiewicz A.

Fundamenta Informaticae

2007

Vol. 79, nr 3-4

487-495

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.

An Efficient Message Passing Election Algorithm based on Mazurkiewicz's Algorithm

Chalopin J., Métivier Y.

Fundamenta Informaticae

2007

Vol. 80, nr 1-3

221-246

We study the election and the naming problems in the asynchronous message passing model. We present a necessary condition based on Angluin's lifting lemma [1] that must be satisfied by any network that admits a naming (or an election) algorithm. We then show that this necessary condition is also sufficient: we present an election and naming algorithm based on Mazurkiewicz's algorithm [17]. The algorithm we obtained is totally asynchronous and it needs a polynomial number of messages of polynomial size, whereas previous election algorithms in this model are pseudo-synchronous and use messages of exponential size.

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

Chalopin J., Métivier Y., Zielonka W.

Fundamenta Informaticae

2006

Vol. 74, nr 1

85-114

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.