A SELF-STABILIZING DISTRIBUTED ALGORITHM FOR MINIMAL SPANNING TREE PROBLEM IN A SYMMETRICAL GRAPH

Authors
ANTONOIU G SRIMANI PK
Citation
G. Antonoiu et Pk. Srimani, A SELF-STABILIZING DISTRIBUTED ALGORITHM FOR MINIMAL SPANNING TREE PROBLEM IN A SYMMETRICAL GRAPH, Computers & mathematics with applications, 35(10), 1998, pp. 15-23
Citations number
16
Categorie Soggetti
Mathematics,"Computer Science Interdisciplinary Applications",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Computers & mathematics with applications → ACNP
ISSN journal
08981221
Volume
35
Issue
10
Year of publication
1998
Pages
15 - 23
Database
ISI
SICI code
0898-1221(1998)35:10<15:ASDAFM>2.0.ZU;2-P
Abstract
Minimal Spanning Tree (MST) problem in an arbitrary undirected graph i s 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 pr oblem and to prove its correctness. The algorithm utilizes an interest ing result of [1]. We show the correctness of the proposed algorithm b y using a new technique involving induction. (C) 1998 Elsevier Science Ltd. All rights reserved.