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:
- 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.
- If u has a (X,j)-labelled neighbours with j>i then u
becomes neutral.
- 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.