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

Halina Bielak, Michał Pańczyk


This paper presents a linear time self-stabilizing algorithm for detecting the set offundamental 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 thatthe depth-search spanning tree of the graph is given. The output is given in a distributed manner asa state of variables in the nodes.

Full Text:


DOI: http://dx.doi.org/10.2478/v10065-012-0038-7
Date of publication: 2015-01-04 00:00:00
Date of submission: 2016-04-28 09:09:36


Total abstract view - 589
Downloads (from 2020-06-17) - PDF - 0



  • There are currently no refbacks.

Copyright (c) 2015 Annales UMCS Sectio AI Informatica

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.