Faster Algorithms for Computing the R* Consensus Tree

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(n^{2} \sqrt{\log n})$$

time when

$$k = 2$$

(ref. [

10

]) and

$$O(k n^{3})$$

time when

$$k \ge 3$$

(ref. [

4

]). This paper shows how to compute it in

$$O(n^{2})$$

time for

$$k = 2$$

,

$$O(n^{2} \log ^{4/3} n)$$

time for

$$k = 3$$

, and

$$O(n^{2} \log ^{k+2} n)$$

time for unbounded

$$k$$

.