Geodesic
Classes of graphs reconstructed with
Prikladnaâ diskretnaâ matematika, no. 12 (2010), pp. 99-101.

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

A graph exploration problem is considered by means of an agent which moves on graph edges, coloures the marks on it's nodes and its incidentors. The agent reconstructs a graph which is isomorphic to the recognized one by using information about marks on graph nodes and incidentors. A proposed recognition methods have quadratic and cubic complexity and need no more then four different marks. Classes of graphs with linear complexity of recognition are found. For them some operations on graphs preserving the linear complexity of recognition are defined. 
@article{PDM_2010_12_a51,
     author = {E. A. Tatarinov},
     title = {Classes of graphs reconstructed with},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {99--101},
     publisher = {mathdoc},
     number = {12},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2010_12_a51/}
}
TY  - JOUR
AU  - E. A. Tatarinov
TI  - Classes of graphs reconstructed with
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2010
SP  - 99
EP  - 101
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2010_12_a51/
LA  - ru
ID  - PDM_2010_12_a51
ER  - 
%0 Journal Article
%A E. A. Tatarinov
%T Classes of graphs reconstructed with
%J Prikladnaâ diskretnaâ matematika
%D 2010
%P 99-101
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2010_12_a51/
%G ru
%F PDM_2010_12_a51
E. A. Tatarinov. Classes of graphs reconstructed with. Prikladnaâ diskretnaâ matematika, no. 12 (2010), pp. 99-101. http://geodesic.mathdoc.fr/item/PDM_2010_12_a51/

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

[2] 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 | MR

[3] 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

[4] Kasyanov V. N., Evstigneev V. A., Grafy v programmirovanii, vizualizatsiya i primenenie, Peterburg, SPb., 2003