✦ LIBER ✦

A self-stabilizing algorithm which finds a 2-center of a tree

✍ Scribed by Tetz C. Huang; Ji-Cherng Lin; Hsueh-Jen Chen

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 884 KB
Volume: 40
Category: Article
ISSN: 0898-1221
DOI: 10.1016/s0898-1221(00)00183-8

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we design a self-stabilizing algorithm which finds a 2-center for a distributed system with a tree topology. Our algorithm is based on the algorithm in [1][2][3]. The latter enables us to find the center (or centers) for the tree. If we sever the tree at the center (or centers), we obtain two subtrees. One of the major works in this paper is to show that if we pick a center from each subtree, the two picked centers will constitute a 2-center for the original tree. With this in mind, we design our algorithm so that it is equipped with the ability of "sensing" the two subtrees and then finding a center in each of them. (~) 2000 Elsevier Science Ltd. All rights reserved.

📜 SIMILAR VOLUMES

A Self-Stabilizing Leader Election Algor

A Self-Stabilizing Leader Election Algorithm for Tree Graphs

✍ Gheorghe Antonoiu; Pradip K. Srimani 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 231 KB

We propose a self-stabilizing algorithm (protocol) for leader election in a tree graph. We show the correctness of the proposed algorithm by using a new technique involving induction.

A Self-Stabilizing Distributed Algorithm

A Self-Stabilizing Distributed Algorithm to Find the Median of a Tree Graph

✍ Gheorghe Antonoiu; Pradip K. Srimani 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 231 KB

We propose a self-stabilizing algorithm (protocol) for computing the median in a given tree graph. We show the correctness of the proposed algorithm by using a new technique involving induction.

A simple algorithm for finding the cente

A simple algorithm for finding the center of a tree

✍ A. B. Murdasov 📂 Article 📅 1976 🏛 Springer US 🌐 English ⚖ 92 KB

A linear algorithm for finding the k-bro

A linear algorithm for finding the k-broadcast center of a tree

✍ Hovhannes A. Harutyunyan; Arthur L. Liestman; Bin Shao 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

A self-stabilizing algorithm for constru

A self-stabilizing algorithm for constructing spanning trees

✍ Nian-Shing Chen; Hwey-Pyng Yu; Shing-Tsaan Huang 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 663 KB

A self-stabilizing distributed algorithm

A self-stabilizing distributed algorithm for minimal spanning tree problem in a symmetric graph

✍ G. Antonoiu; P.K. Srimani 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 640 KB

Minimal Spanning Tree (MST) problem in an arbitrary undirected graph is an important problem in graph theory and has extensive applications. Numerous algorithms are available to compute an MST. Our purpose here is to propose a self-stabilizing distributed algorithm for the MST problem and to prove i