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).

http://i.stanford.edu/pub/cstr/reports/cs/tr/95/1545/CS-TR-95-1545.pdf