Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-15775-2_49
Title: Constructing the R* consensus tree of two trees in subcubic time
Authors: Jansson, J.
Sung, W.-K. 
Issue Date: 2010
Source: Jansson, J.,Sung, W.-K. (2010). Constructing the R* consensus tree of two trees in subcubic time. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6346 LNCS (PART 1) : 573-584. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-15775-2_49
Abstract: The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees T 1 and T 2 with a leaf label set of cardinality n run in Θ(n 3) time [3,8]. In this manuscript, we describe a new O(n 2 log n)-time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set ℛ maj which may contain Ω(n 3) elements, so any direct approach which explicitly constructs ℛ maj requires Ω(n 3) time. © 2010 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/41174
ISBN: 3642157742
ISSN: 03029743
DOI: 10.1007/978-3-642-15775-2_49
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

2
checked on Dec 13, 2017

Page view(s)

46
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.