Improved algorithm for the symmetry number problem on trees

The symmetry number of a tree is defined as the number of nodes of the maximum subtree of the tree that exhibits axial symmetry. The best previous algorithm for computing the symmetry number for an unrooted unordered tree is due to [P.P. Mitra, M.A.U. Abedin, M.A. Kashem, Algorithms for solving the symmetry number problem on trees, Inform. Process. Lett. 91 (2004) 163-169] and runs in O(n³) time. In this paper we show an improvement on this time complexity by encoding small trees. Our algorithm runs in time O(n³²(loglogn/logn)).