Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: DFS spanning tree

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.