Faster Algorithms for Computing the R* Consensus Tree

Jesper Andreas Jansson, Wing Kin Sung, Hoa Vu, Siu Ming Yiu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


The fastest known algorithms for computing the R* consensus tree of k rooted phylogenetic trees with n leaves each and identical leaf label sets run in O(n2logn) time when k= 2 (Jansson and Sung in Algorithmica 66(2):329–345, 2013) and O(kn3) time when k≥ 3 (Bryant in Bioconsensus, volume 61 of DIMACS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp 163–184, 2003). This paper shows how to compute it in O(n2) time for k= 2 , O(n2log4 / 3n) time for k= 3 , and O(n2logk+2n) time for unbounded k.
Original languageEnglish
Pages (from-to)1224-1244
Number of pages21
Issue number4
Publication statusPublished - 1 Dec 2016
Externally publishedYes


  • Apresjan cluster
  • Phylogenetic tree
  • R* consensus tree
  • Strong cluster
  • Triplet

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Faster Algorithms for Computing the R* Consensus Tree'. Together they form a unique fingerprint.

Cite this