- Tytuł:
- A self-stabilizing algorithm for detecting fundamental cycles in a graph with DFS spanning tree given
- Autorzy:
-
Bielak, H.
Pańczyk, M. - Powiązania:
- https://bibliotekanauki.pl/articles/106174.pdf
- Data publikacji:
- 2013
- Wydawca:
- Uniwersytet Marii Curie-Skłodowskiej. Wydawnictwo Uniwersytetu Marii Curie-Skłodowskiej
- Tematy:
-
self-stabilizing algorithm
fundamental cycles
graph
DFS spanning tree - Opis:
- 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.
- Źródło:
-
Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica; 2013, 13, 1; 7-10
1732-1360
2083-3628 - Pojawia się w:
- Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
- Dostawca treści:
- Biblioteka Nauki
Artykuł