A 3-degree (binary) tree
with unique labels on the leaves
and with edge weights
A 3-degree tree T' with the
same set of unique labels as T.
A sequence of edges
representing nearest neighbour
interchanges transforming the tree T into T' (so that the labels match).
A nearest neighbour interchange of
is a transformation where
one of the two subtrees adjacent to u is exchanged with one of the two
subtrees adjacent to v.
The cost of the sequence of interchanges, i.e.,
where n is the number of leaves
The variation when another type of transformation called linear-cost
subtree transfer is used is approximable within 2
MAXIMUM AGREEMENT SUBTREE for three trees of unbounded degree is
not approximable within
for any ,
unless NPQP .