Geodesic
Graph reconstruction by automata team
Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 97-98.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is devoted to analysis and modification of the Basic Algorithm for graph reconstruction by agent, moving through graph edges, reading and modifying marks on the elements of the graph. The algorithm uses an implicit enumeration of graph vertices. The modification of the Basic Algorithm implements the reconstruction by automata team. In this case, the upper bound on the time complexity of the algorithm depends on the number of agents in the automata team that perform the reconstruction. 
@article{PDMA_2012_5_a51,
     author = {E. A. Tatarinov},
     title = {Graph reconstruction by automata team},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {97--98},
     publisher = {mathdoc},
     number = {5},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2012_5_a51/}
}
TY  - JOUR
AU  - E. A. Tatarinov
TI  - Graph reconstruction by automata team
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2012
SP  - 97
EP  - 98
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2012_5_a51/
LA  - ru
ID  - PDMA_2012_5_a51
ER  - 
%0 Journal Article
%A E. A. Tatarinov
%T Graph reconstruction by automata team
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2012
%P 97-98
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2012_5_a51/
%G ru
%F PDMA_2012_5_a51
E. A. Tatarinov. Graph reconstruction by automata team. Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 97-98. http://geodesic.mathdoc.fr/item/PDMA_2012_5_a51/

[1] Dudek G., Jenkin M., Computational principles of mobile robotic, Cambridge Univ. Press, 2000, 280 pp. | Zbl

[2] Tatarinov E. A., “M-numeratsiya, kak metod raspoznavaniya grafov”, Zbrnik naukovikh prats “Pitannya prikladnoï matematiki ta matematichnogo modelyuvannya”, 2010, 260–272

[3] Grunskii I. S., Tatarinov E. A., “Raspoznavanie konechnogo grafa bluzhdayuschim po nemu agentom”, Vestnik Donetskogo universiteta. Ser. A. Estestvennye nauki, 2009, no. 1, 492–497

[4] Tatarinov E. A., “Bazovyi algoritm vosstanovleniya grafa”, Trudy IPMM NAN Ukrainy, 21, 2010, 216–227 | Zbl

[5] Kharari F., Teoriya grafov, Mir, M., 1973, 300 pp. | MR