This paper presents a self stabilizing algorithm for detecting a set of fundamental cycles of a connected undirected graph on an asynchronous dis- tributed or network model of computation. The output of the algorithm is available in a distributed manner; i.e., when the algorithm terminates each node of the graph knows exactly how many fundamental cycles are passing through it and also a unique identifier for each of these fundamental cycles. The algorithm is resilient to transient faults and does not require initializa- tion. It has been proved that the algorithm is correct and requires O(n~2) time if the depth-first search spanning tree of the graph is known, or else it requires O(n~3) time, where n is the number of nodes in the graph.
展开▼
