Self-stabilizing tree ranking

Abstract

Given a graph G and some property ℘ (g), a ℘-ranking (ordering) of the nodes of G can be defined as a one-to-one function from V to {1, 2, 3, …, n} such that property ℘(G) holds for each node i∈V. In this paper we present an O(n ²) self-stabilizing algorithm which, when given a rooted tree T, will provide ℘-rankings consistent with the following standard graph traversal properties: (i) preorder traversal; (ii) postorder traversal; (iii) reverse-postorder traversal; (iv) breadth-first traversal; (v) breadth–depth traversal.

Keywords:

• Distributed system
• Self-stabilizing algorithm
• Tree traversal
• Rank
• Complexity