×

zbMATH — the first resource for mathematics

On the computational complexity of the rooted subtree prune and regraft distance. (English) Zbl 1059.05035
The paper proves that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard – solving a longstanding problem. (This operation cuts off a subtree and reattaches it to another part of the tree.)

MSC:
05C05 Trees
92D15 Problems related to evolution
PDF BibTeX XML Cite
Full Text: DOI