Analysis of a Graph by a Set of Automata.
Authors
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 pdfKeywords
Edition
Programming and Computer Software, 41(6):307-310, 2015.
DOI: 10.1134/S0361768815060031