A SELF-STABILIZING DISTRIBUTED ALGORITHM TO CONSTRUCT BFS SPANNING TREES OF A SYMMETRIC GRAPH

1 September 1992

journal article
Published by World Scientific Pub Co Pte Ltd in Parallel Processing Letters

Vol. 2 (2) , 171-179
https://doi.org/10.1142/s0129626492000295

Abstract

We propose a simple and efficient self-stabilizing distributed algorithm to construct the breadth first search (BFS) spanning tree of an arbitrary connected symmetric graph. We develop a completely new direct approach of graph theoretical reasoning to prove the correctness of our algorithm. The approach seems to have potential to have applications in proving correctness of other self-stabilizing algorithms for graph theoretical problems.

Keywords

ALGORITHMS FOR GRAPH
STABILIZING DISTRIBUTED ALGORITHM
SPANNING TREE
CONSTRUCT BFS
SYMMETRIC GRAPH

This publication has 0 references indexed in Scilit: