Next: MAXIMUM COMMON POINT SET
Up: Compression and Representation
Previous: LONGEST COMMON SUBSEQUENCE
  Index
- INSTANCE:
Collection
of trees.
- SOLUTION:
A tree T' isomorphic to a subtree (i.e. induced connected subgraph)
of each Ti.
- MEASURE:
Size, i.e. number of nodes, of the common subtree T'.
- Good News:
Approximable within
,
where n is the size of
the smallest Ti [7].
- Bad News:
Not approximable within
for any
[7].
- Comment:
Transformation from MAXIMUM INDEPENDENT SET.
hardness holds for the variation where the nodes are labeled
and where maximum degree is bounded by a constant
.
Approximable within
when the maximum degree is
constant.
Variation in which the nodes are labeled is approximable within
if the number of distinct labels is
O(logO(1)n) and within
in general [7].
Approximable within 2 if the solution is an isomorphic edge subset of each
tree.
APX-hard when the number of input trees is a constant at least 3, but
polynomial-time solvable if the maximum degree is additionally bounded
by constant or for only two trees [6].
Next: MAXIMUM COMMON POINT SET
Up: Compression and Representation
Previous: LONGEST COMMON SUBSEQUENCE
  Index
Viggo Kann
1999-04-22