Next: MINIMUM GRAPH TRANSFORMATION
Up: Iso- and Other Morphisms
Previous: MAXIMUM COMMON INDUCED SUBGRAPH
with labels on the nodes.
A common embedded sub-tree, i.e. a labeled tree T' that can be embedded
An embedding from T' to T is an injective
function from the nodes of T' to the nodes of T that preserves labels
and ancestorship. Note that since fathership does not need to be preserved,
T' does not need to be an ordinary subtree.
Cardinality of the common embedded sub-tree, i.e., .
- Good News:
Approximable within ,
where n is the number of nodes in the trees
- Bad News:
Transformation from MAXIMUM K-SET PACKING.
Variation in which the problem is to minimize the edit distance between
the two trees is also APX-hard.