A general approach to solving problems on graphs by collective automata

We propose a general method to solve graph problems by a set of automata (computational agents) located in vertices of undirected ordered connected rooted graph and communicating by passing messages along graph edges. The automata are semi-robots, i.e., their internal memory size is sufficient to store values depending on the number of vertices and edges of the graph ($n$ and $m$, correspondingly) but is too small to store the complete graph description. Section 2 presents classification of graph-based distributed computational models depending on internal memory size of vertex automaton, vertex automaton operation time, and edge capacity (the number of messages that are passing along an edge simultaneously). We choose for further use the model of maximum parallelism, having zero automaton operation time and unbounded edge capacity. It allows to obtain lower complexity bounds on distributed graph problems. Section 3 describes algorithm complexity assessment rules. Section 4 presents basic message processing procedures and message classification according to paths passed by them and methods of message processing by vertex automaton. We propose to construct algorithms solving graph problems on the base of the procedures considered, and present some examples in further sections. Sections 5-9 describe distributed algorithms for spanning tree construction, for task termination detection (based on detection of absence of messages used by the task), for shortest paths tree construction, for graph vertices enumeration, for collecting graph structure information in the root automaton memory (if it is unbounded). The algorithms proposed has linear time complexity in $n$ and $m$, and use linear in $n$ and $m$ number of messages. Section 10 considers construction of maximum weight path in a weighted graph, which is the NP problem. We propose the algorithm that for the sake of using unbounded number of messages can solve this problem in linear time in $n$ and $m$. The conclusion summarizes the paper and draws directions of further research: constructing algorithms for other graph problems and generalization of the approach to directed, non-deterministic and dynamic graphs.