Mazurkiewicz's Universal Graph Reconstruction Algorithm



Mazurkiewicz's algorithm is a distributed algorithm for enumerating nodes in an anonymous covering-minimal graph when its size is known. A distributed enumeration algorithm on a graph G is a distributed algorithm such that the result of any computation is a labelling of the vertices that is a bijection from V(G) to {1,2,...,|V(G)|}.



An application of a transformation rule is done on a subgraph defined by a vertex v and the set of vertices adjacent to v; the application of a rule :
  • depends on the label of v and the labels of nodes adjacent to v,
  • it changes the label of v and the labels of nodes adjacent to v.


Snapshots