A Self-Stabilizing Algorithm for Detecting Fundamental Cycles in a Graph

摘要

This paper presents a self-stabilizing algorithm for detecting a set of fundamental cycles of a connected undirected graph on an asynchronous distributed 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 initialization. It has been proved that the algorithm is correct and requires O(n2) time if the depth-first search spanning tree of the graph is known, or else it requires O(n3) time, where n is the number of nodes in the graph.