Abstract
In this thesis, a space efficient, self-stabilizing algorithm for finding biconnected components, articulation points, and bridges of an undirected graph is proposed.An algorithm is self-stabilizing if executing the algorithm brings the system into a set of legitimate states in bounded time, and the system stays in the legitimate states thereafter. Self-stabilizing algorithms have the desirable properties that no initialization is needed for the system, and the system can recover from transient failures.There are many works related to the biconnecticity problem, but all known self-stabilizing solutions to the problem have a space complexity of O(nlogn), where n is the total number of processes in the system. Our main contribution is to provide a self-stabilizing algorithm with a space complexity of O(dlogn), where d is the maximum degree of the nodes in the system.The algorithm starts with constructing a breadth-first spanning tree in the first layer, and ends with edge coloring in the final layer. The edges having the same color belongs to the same biconnected component. This edge color information can be used to determine biconnected components, articulation points, and bridges of the graph.