BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-95-1545
       ENTRY:: February 14, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Approximation Algorithms for the Largest Common Subtree
               Problem.
        TYPE:: Technical Report
      AUTHOR:: Khanna, Sanjeev
      AUTHOR:: Motwani, Rajeev
      AUTHOR:: Yao, Frances F.
        DATE:: February 1995
       PAGES:: 6
    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).
       NOTES:: [Adminitrivia V1/Prg/19950214]
         END:: STAN//CS-TR-95-1545