A self-stabilizing algorithm for the st-order problem
A self-stabilizing algorithm for the st-order problem
复制标题
一种解决st阶问题的自稳定算法
DOI：
10.1080/17445760701536134
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
H. Thompson
中科院分区：
文献类型：
--
作者：
P. Chaudhuri;H. Thompson
给定一个具有n个结点和一对唯一结点S和t的双连通图G，st-排序将S赋值为1，t赋值为n，并且每隔一个结点分配一个介于2和n−1(包括2和n)之间的整数，使得它具有至少一个具有较小数目的邻居和至少一个具有较大数目的邻居。本文提出了一种自稳定的分布式算法，给G分配一个st-序，证明了该算法至多需要O(Nlogn)轮就能收敛到正确的解。
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.