Linear-time recognition of tree-pictures isomorphism
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part II, Tome 137 (1984), pp. 80-86
Citer cet article
Voir la notice du chapitre de livre 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.