Building direct and back spanning trees by automata on a graph

Abstract

The paper presents a parallel graph exploration algorithm. Automaton on a graph is an analogue of the Turing machine тАФ tape cells correspond to graph vertices, where the automaton can store some data, and moves along the tape correspond to moves along graph arcs. This system can be considered also as an aggregate of finite automatons located in graph vertices and interacting by message sending. Each automaton changes its state according to the data stored in the corresponding vertex, and moves along graph arcs are replaced with messages sent by the automaton of the arcтАЩs starting vertex to the one of the ending vertex. The suggested parallel graph exploration algorithm has worst case working time bound O(n/k+D), where n is the number of vertices, and D is the graph diameter, the maximum length of simple path (non-self intersecting path). As a result the algorithm builds two spanning trees of the graph: the direct spanning tree, which has the root vertex as its tree root and is directed from the root, and the back spanning tree, directed to the root.