Abstract
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: [email protected]
Notes
†E-mail: [email protected]