✦ LIBER ✦

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

✍ Scribed by G. Antonoiu; P.K. Srimani

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 640 KB
Volume: 35
Category: Article
ISSN: 0898-1221
DOI: 10.1016/s0898-1221(98)00068-6

No coin nor oath required. For personal study only.

✦ Synopsis

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 its correctness. The algorithm utilizes an interesting result of [1]. We show the correctness of the proposed algorithm by using a new technique involving induction.

📜 SIMILAR VOLUMES

A self-stabilizing distributed algorithm

A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks

✍ H. Baala; O. Flauzac; J. Gaber; M. Bui; T. El-Ghazawi 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 388 KB

Spanning trees help removing cycles and establishing short paths between a given node and the rest of the nodes in a network. In ad hoc mobile computing networks, however, transient node failures occur due to being out of range or powered off. Therefore, we present a self-stabilized distributed algo

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 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

An efficient distributed algorithm for c

An efficient distributed algorithm for centering a spanning tree of a biconnected graph

✍ R.F.M. Aranha; C.Pandu Rangan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 537 KB

A self-stabilizing algorithm for the sho

A self-stabilizing algorithm for the shortest path problem in a distributed system

✍ Tetz C. Huang; Ji-Cherng Lin 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 352 KB

In this paper, we propose a self-stabilizing algorithm for finding shortest paths in a distributed system in which a central daemon is assumed. The correctness of the proposed algorithm is proved by using the bounded function technique.

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.