scientific article; zbMATH DE number 1302179

From MaRDI portal
Publication:4247446





An evolutionary tree is an unordered tree with labelled leaves, but unlabelled inner nodes. They may be rooted or not, with edge-lengths or not. Several distance measures between such trees on a fixed leave-set are surveyed, all defined as the minimum number of steps needed to transform one tree into the other, of some basic transformation operation like the interchange of the subtrees rooted in two neighbouring nodes. For each distance calculation is shown to be generally NP-hard, and an approximation scheme with guaranteed optimality ratio is described. For the entire collection see [Zbl 0914.90001].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247446)