Geodesic
Deterministic labelling of graph vertices by walking agent
Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 89-91 
I. S. Grunsky; S. V. Sapunov. Deterministic labelling of graph vertices by walking agent. Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 89-91. http://geodesic.mathdoc.fr/item/PDMA_2012_5_a45/
@article{PDMA_2012_5_a45,
     author = {I. S. Grunsky and S. V. Sapunov},
     title = {Deterministic labelling of graph vertices by walking agent},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {89--91},
     year = {2012},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2012_5_a45/}
}
TY  - JOUR
AU  - I. S. Grunsky
AU  - S. V. Sapunov
TI  - Deterministic labelling of graph vertices by walking agent
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2012
SP  - 89
EP  - 91
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/PDMA_2012_5_a45/
LA  - ru
ID  - PDMA_2012_5_a45
ER  - 
%0 Journal Article
%A I. S. Grunsky
%A S. V. Sapunov
%T Deterministic labelling of graph vertices by walking agent
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2012
%P 89-91
%N 5
%U http://geodesic.mathdoc.fr/item/PDMA_2012_5_a45/
%G ru
%F PDMA_2012_5_a45

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

This paper is devoted to the problem of on-line labelling of graph vertices by walking agent so that all vertices in the neighbourhood of the current vertex have different labels (i.e. deterministic labelling). This problem arises in the navigation of mobile robots using topological maps of an environment. Here, a method for deterministic labelling is proposed for an agent of two types differing by the size of the observed neighbourhood of the current vertex.

[1] Dudek G., Jenkin M., Computational Principles of Mobile Robotics, Cambridge University Press, Cambridge, 2000 | Zbl

[2] Zykov A. A., Osnovy teorii grafov, Vuzovskaya kniga, M., 2004