Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

A self-stabilizing algorithm for detecting fundamental cycles in a graph with DFS spanning tree given

Bielak H., Pańczyk M.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

2013

Vol. 13, no. 1

7--10

This paper presents a linear time self-stabilizing algorithm for detecting the set of fundamental cycles on an undirected connected graph modelling asynchronous distributed system.The previous known algorithm has O(n^2) time complexity, whereas we prove that this one stabilizesafter O(n) moves. The distributed adversarial scheduler is considered. Both algorithms assume that the depth-search spanning tree of the graph is given. The output is given in a distributed manner asa state of variables in the nodes.

A self–stabilizing algorithm for finding weighted centroid in trees

Bielak H., Pańczyk M.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

2012

Vol. 12, no. 2

27--37

In this paper we present some modification of the Blair and Manne algorithm for finding the center of a tree network in the distributed, self-stabilizing environment. Their algorithm finds n/2 -separator of a tree. Our algorithm finds weighted centroid, which is direct generalization of the former one for tree networks with positive weights on nodes. Time complexity of both algorithms is O(n2), where n is the number of nodes in the network.