Algorithms for the Majority Rule (+) Consensus Tree and the Frequency Difference Consensus Tree

This article presents two new deterministic algorithms for constructing consensus trees. Given an input of <tex-math notation="LaTeX">k</tex-math><alternatives> </alternatives> phylogenetic trees with identical leaf label sets and <tex-math notation="LaTeX">n</tex-math><alternatives> </alternatives> leaves each, the first algorithm constructs the majority rule (+) consensus tree in <tex-math notation="LaTeX">$O(k n)$</tex-math><alternatives> </alternatives> time, which is optimal since the input size is <tex-math notation="LaTeX">Ω (k n)</tex-math><alternatives> </alternatives>, and the second one constructs the frequency difference consensus tree in <tex-math notation="LaTeX">min O(k n²), O(k n (k + log ²n))</tex-math><alternatives> </alternatives> time.