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

摘要

This paper presents a linear time quasi self-stabilizing algorithm for detecting the set of fundamental cycles on an undirected connected graph modeling asynchronous distributed system. Previous known algorithm has O(n2) time complexity, whereas we prove that our stabilizes after O(n) moves. Distributed adversarial scheduler is considered. Both algorithms assume that the depth-first search (DFS) spanning tree (DFST) of the graph is given. The output is given in a distributed manner as a state of variables in the nodes.