Geodesic
On a new complete invariant for acyclic graphs
Prikladnaâ diskretnaâ matematika, no. 12 (2010), pp. 97-98 
A. V. Prolubnikov. On a new complete invariant for acyclic graphs. Prikladnaâ diskretnaâ matematika, no. 12 (2010), pp. 97-98. http://geodesic.mathdoc.fr/item/PDM_2010_12_a49/
@article{PDM_2010_12_a49,
     author = {A. V. Prolubnikov},
     title = {On a~new complete invariant for acyclic graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {97--98},
     year = {2010},
     number = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2010_12_a49/}
}
TY  - JOUR
AU  - A. V. Prolubnikov
TI  - On a new complete invariant for acyclic graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2010
SP  - 97
EP  - 98
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/PDM_2010_12_a49/
LA  - ru
ID  - PDM_2010_12_a49
ER  - 
%0 Journal Article
%A A. V. Prolubnikov
%T On a new complete invariant for acyclic graphs
%J Prikladnaâ diskretnaâ matematika
%D 2010
%P 97-98
%N 12
%U http://geodesic.mathdoc.fr/item/PDM_2010_12_a49/
%G ru
%F PDM_2010_12_a49

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

A new complete invariant for acyclic graphs is presented. An algorithm for solution of the graph isomorphism problem is considered. The algorithm is based on the invariant and gives solution of the problem for a wide graph class.

[1] Balasubramanian K., Parthasarathy K. R., “In search of a complete invariant for graphs”, Lect. Notes Mathem., 885, 1981, 42–59 | MR | Zbl

[2] Lindell S., “A Logspace Algorithm for Tree Canonization”, Proc. of the 24th Annual ACM Symposium on the Theory of Computing, ACM, New York, 1992, 400–404

[3] Datta S., Limaye N., Nimbhorkar P., Thierauf T., Wagner F., “Planar Graph Isomorphism is in Log-Space”, 24th Annual IEEE Conference on Computational Complexity (Paris, France, July 15 –July 18 2009)