A self-stabilizing graph algorithm: Finding the cutting center of a tree

The cutting number of a node i in a connected graph G is the number of pairs of nodes in different components of G − {i}. The cutting center consists of the set of nodes of G with maximal cutting number. This article presents a self-stabilizing algorithm for finding the cutting numbers for all nodes of a tree T = (V T, E T) and hence the cutting center of T. It is shown that the proposed self-stabilizing algorithm requires O(n 2) moves. The algorithm complexity can also be expressed as O(n) rounds. †E-mail: hthompson@uwichill.edu.bb