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

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 ²) moves. The algorithm complexity can also be expressed as O(n) rounds.

^†E-mail: [email protected]

Keywords:

• Distributed system
• Self-stabilizing algorithm
• Tree
• Cutting center
• Complexity

Notes

^†E-mail: [email protected]