Geodesic
Linear-time recognition of tree-pictures isomorphism
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part II, Tome 137 (1984), pp. 80-86

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

Tree-picture is an image of a tree on the plane. The isomorphism of tree-pictures is considered as the coincidence of the Images up to an isotopy of the plane. This notion suits more the pattern-recognition problems, rather than the isomorphism of the trees as abstract graphs. Tree-picture is determined (up to an isomorphism) by local orientations of its vertices, i. e. for each vertex corresponds a list of adjacent edges in the clockwise order. A linear-time algorithm for finding the maximal (relatively to the lexicographical order) among the strings, whose letters are integers, cyclically equal to a given one, is suggested. Basing on it a linear-time recognising of tree-pictures is produced. 
@article{ZNSL_1984_137_a3,
     author = {A. N. Grigor'eva},
     title = {Linear-time recognition of tree-pictures isomorphism},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {80--86},
     publisher = {mathdoc},
     volume = {137},
     year = {1984},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a3/}
}
TY  - JOUR
AU  - A. N. Grigor'eva
TI  - Linear-time recognition of tree-pictures isomorphism
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1984
SP  - 80
EP  - 86
VL  - 137
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a3/
LA  - ru
ID  - ZNSL_1984_137_a3
ER  - 
%0 Journal Article
%A A. N. Grigor'eva
%T Linear-time recognition of tree-pictures isomorphism
%J Zapiski Nauchnykh Seminarov POMI
%D 1984
%P 80-86
%V 137
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a3/
%G ru
%F ZNSL_1984_137_a3
A. N. Grigor'eva. Linear-time recognition of tree-pictures isomorphism. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part II, Tome 137 (1984), pp. 80-86. http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a3/