A SELF-STABILIZING DISTRIBUTED ALGORITHM TO CONSTRUCT AN ARBITRARY SPANNING TREE OF A CONNECTED GRAPH

Authors
ANTONOIU G SRIMANI PK
Citation
G. Antonoiu et Pk. Srimani, A SELF-STABILIZING DISTRIBUTED ALGORITHM TO CONSTRUCT AN ARBITRARY SPANNING TREE OF A CONNECTED GRAPH, Computers & mathematics with applications, 30(9), 1995, pp. 1-7
Citations number
10
Categorie Soggetti
Computer Sciences",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Computers & mathematics with applications → ACNP
ISSN journal
08981221
Volume
30
Issue
9
Year of publication
1995
Pages
1 - 7
Database
ISI
SICI code
0898-1221(1995)30:9<1:ASDATC>2.0.ZU;2-J
Abstract
We propose a simple self-stabilizing distributed algorithm that mainta ins an arbitrary spanning tree in a connected graph. In proving the co rrectness of the algorithm, we develop a new technique without using a bounded function (which is customary for proving correctness of self- stabilizing algorithms); the new approach is simple and can be potenti ally applied to proving correctness of other self-stabilizing algorith ms.