Report Number: CS-TR-95-1545
Institution: Stanford University, Department of Computer Science
Title: Approximation Algorithms for the Largest Common Subtree Problem.
Author: Khanna, Sanjeev
Author: Motwani, Rajeev
Author: Yao, Frances F.
Date: February 1995
Abstract: The largest common subtree problem is to find a largest subtree which occurs as a common subgraph in a given collection of trees. We show that in case of bounded degree trees, we can achieve an approximation ratio of O(( n*loglog n ) / log^{2} n). In case of unbounded degree nodes, we give an algorithm with approximation ratio O(( n*(loglog n)^{2}) / log^{2} n) when the trees are unlabeled. An approximation ratio of O(( n*(loglog n)^{2} ) / log^{2} n) is also achieved for the case of labeled unbounded degree trees provided the number of distinct labels is O(log^{O(1)} n).