Approximation Algorithms for the Largest Common Subtree Problem

摘要

The largest common subtree problem is to find a largest tree which occurs as acommon subgraph in a given collection of trees. Let n denote the number of vertices in the largest tree in the collection. We show that in the case of bounded degree trees, it is possible to achieve an approximation ratio of O(n(log log n)/log squared n). For unbounded degree trees, we give an algorithm with approximation ratio O(n(log log n) squared/log squared n) when the trees are unlabeled. An approximation ratio of O(n(log log n) squared/log squared n) is also achieved for the case of labeled unbounded degree trees provided the number of distinct labels is O(log sup O(1) n).