Geodesic
Graph recognition by moving agent
Prikladnaâ diskretnaâ matematika, no. 10 (2009), pp. 96-98.

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

A graph recognition problem is considered by means of agent which moves on graph edges, marks on its nodes and incidentors. A recognition method is proposed in which an agent builds not exploring graph. The method requires two different marks and one pebble, and its number of steps is cubic function from number of graph nodes. 
@article{PDM_2009_10_a49,
     author = {I. S. Grunskii and E. A. Tatarinov},
     title = {Graph recognition by moving agent},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {96--98},
     publisher = {mathdoc},
     number = {10},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2009_10_a49/}
}
TY  - JOUR
AU  - I. S. Grunskii
AU  - E. A. Tatarinov
TI  - Graph recognition by moving agent
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2009
SP  - 96
EP  - 98
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2009_10_a49/
LA  - ru
ID  - PDM_2009_10_a49
ER  - 
%0 Journal Article
%A I. S. Grunskii
%A E. A. Tatarinov
%T Graph recognition by moving agent
%J Prikladnaâ diskretnaâ matematika
%D 2009
%P 96-98
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2009_10_a49/
%G ru
%F PDM_2009_10_a49
I. S. Grunskii; E. A. Tatarinov. Graph recognition by moving agent. Prikladnaâ diskretnaâ matematika, no. 10 (2009), pp. 96-98. http://geodesic.mathdoc.fr/item/PDM_2009_10_a49/

[1] Kapitonova Yu. V., Letichevskii A. A., Matematicheskaya teoriya programmirovaniya vychislitelnykh sistem, Nauka, M., 1988, 296 pp. | MR | Zbl

[2] Kudryavtsev V. B., Uschumlich Sh., Kilibarda G., “O povedenii avtomatov v labirintakh”, Diskretnaya matematika, 4:3 (1992), 3–28 | MR | Zbl

[3] Kuipers B., “The spatial semantic hierarchy”, Artifical Intellegence, 119:1–2 (2000), 191–233 | DOI | MR | Zbl

[4] Evstigneev V. A., Primenenie teorii grafov v programmirovanii, Nauka, M., 1985, 352 pp. | MR

[5] Grunskii I. S., Tatarinov E. A., “Algoritm raspoznavaniya grafov”, Trudy Chetvertoi Mezhdunar. konf. “Parallelnye vychisleniya i zadachi upravleniya” PACO'2008, Institut problem upravleniya im. V. A. Trapeznikova RAN, M., 2008, 1483–1498