Sequential Computation of a Spanning Tree, Each Process is Identified by a Unique Name



Description:

Let G be a graph with n vertices. Each vertex has an unique identity; i.e. a unique number between 1 and n. Initially all edges are labelled 0 and each vertex is labelled (A,i) where i is its identity. At each step of the computation, the (A,i)-labelled vertex, say u, will act as follows:
  1. If u has a (X,j)-labelled neighbour v, where j<i and X={A,M,N,F}, then u will activate this neighbour: u becomes marked (with label (M,i)), v becomes active (with label (A,i)) and the edge {u,v} becomes i-labelled.
  2. If u has a (X,j)-labelled neighbours with j>i then u becomes neutral.
  3. If u has no (X,j)-labelled neighbour, where j<i and X = {A,M,N,F}, and has a (unique) (M,i)-labelled neighbour w then u will reactivate this neighbour: u enters a final state (with label (F,i)) and w becomes (A,i)-labelled.
The computation stops as soon as none of the above computation rules may be applied (in that case, all the neighbours of the (A,n)-labelled vertex are (F,n)-labelled). The spanning tree is then given by the set of all n-labelled edges.



Description

Proof

Snapshots