Skip to main content

Research Repository

Advanced Search

Optimizing phylogenetic diversity across two trees

Bordewich, M.; Semple, C.; Spillner, A.


C. Semple

A. Spillner


We present a polynomial-time algorithm for finding an optimal set of taxa that maximizes the weighted sum of the phylogenetic diversity across two phylogenetic trees. This resolves one of the challenges proposed as part of the Phylogenetics Programme held at the Isaac Newton Institute for Mathematical Sciences (Cambridge, 2007). It also completely closes the gap between optimizing phylogenetic diversity on one tree, which is known to be in P, and optimizing phylogenetic diversity across three or more trees, which is known to be NP-hard.


Bordewich, M., Semple, C., & Spillner, A. (2009). Optimizing phylogenetic diversity across two trees. Applied Mathematics Letters, 22(5), 638-641.

Journal Article Type Article
Publication Date May 1, 2009
Deposit Date Dec 21, 2009
Journal Applied Mathematics Letters
Print ISSN 0893-9659
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 22
Issue 5
Pages 638-641
Keywords Phylogenetic diversity.