Constructing the R* consensus tree of two trees in subcubic time

Jesper Andreas Jansson, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)


The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees T1and T2with a leaf label set of cardinality n run in Θ(n3) time [3,8]. In this manuscript, we describe a new O(n2log n)-time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set ℛmajwhich may contain Ω(n3) elements, so any direct approach which explicitly constructs ℛmajrequires Ω(n3) time.
Original languageEnglish
Title of host publicationAlgorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
Number of pages12
EditionPART 1
Publication statusPublished - 19 Nov 2010
Externally publishedYes
Event18th Annual European Symposium on Algorithms, ESA 2010 - Liverpool, United Kingdom
Duration: 6 Sept 20108 Sept 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6346 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th Annual European Symposium on Algorithms, ESA 2010
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • General Computer Science
  • Theoretical Computer Science


Dive into the research topics of 'Constructing the R* consensus tree of two trees in subcubic time'. Together they form a unique fingerprint.

Cite this