A self-stabilizing algorithm for the st-order problem

Abstract

Given a biconnected graph G with n nodes and a pair of unique nodes s and t, an st-ordering assigns s with 1 and t with n, and every other node with an integer between 2 and n − 1 (inclusive) such that it has at least one neighbor with a smaller number and at least one neighbor with a larger number. This paper presents a self-stabilizing distributed algorithm which assigns an st-ordering to G. The algorithm is shown to require at most O(n log n) rounds to converge to a correct solution.

Keywords:

• analysis of algorithms
• distributed systems
• graph algorithms
• graph labeling
• st-order
• st-number

Notes

^1. [email protected]

Additional information

Notes on contributors

Hussein Thompson

1. 1. [email protected]