Next: MAXIMUM FREQUENCY ALLOCATION Up: Miscellaneous Previous: MAXIMUM MAP LABELING Index

### MINIMUM PHYLOGENETIC TREE DISTANCE

- INSTANCE: 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.
- SOLUTION: A sequence of edges representing nearest neighbour interchanges transforming the tree T into T' (so that the labels match). A nearest neighbour interchange of ei={u,v} is a transformation where one of the two subtrees adjacent to u is exchanged with one of the two subtrees adjacent to v.
- MEASURE: The cost of the sequence of interchanges, i.e., .

- Good News: Approximable within where n is the number of leaves [124].
- Comment: The variation when another type of transformation called linear-cost subtree transfer is used is approximable within 2 [124]. MAXIMUM AGREEMENT SUBTREE for three trees of unbounded degree is not approximable within for any , unless NPQP [228].