Ivannikov Institute for System Programming of the RAS


Analysis of a Graph by a Set of Automata.

Authors

I. B. Bourdonov, A. S. Kossatchev, V. V. Kulyamin.

Abstract

This paper describes an algorithm of unknown directed graph exploration (uncovering the full graph structure) performed by unbounded set of finite automata interacting by message passing and moving along the arcs of graph according to their direction. Under the assumption that basic operations of automata works not longer than some fixed time and message transmission takes also less than some fixed time, the algorithm time complexity is O(m+nd), where n is the number of graph vertices, m is the number of graph arcs, d is the graph diameter, and this estimate is strict. The complete proofs of the assertions made in the paper are published in [6].

Full text of the paper in pdf

Keywords

directed graph exploration, distributed algorithm, finite automata agents

Edition

Programming and Computer Software, 41(6):307-310, 2015.

DOI: 10.1134/S0361768815060031

Research Group

Software Engineering

All publications during 2015 All publications