Algorithms for solving 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. Chin and Yen have presented an algorithm for solving the problem of finding the symmetry number of unrooted unordered trees in time O(n⁴). In this paper we present an improved algorithm for solving the symmetry number problem on trees that runs in time O(n³). We also show that our algorithm needs O(n²logn) time for trees with bounded degrees.