A MUL-tree is a generalization of a phylogenetic tree that allows the same leaf label to be used many times. Lott
[9,10] recently introduced the problem of inferring a so-called
from a set of conflicting MUL-trees and gave an exponential-time algorithm for a special greedy variant. Here, we study
majority rule consensus MUL-trees
, and present the first ever polynomial-time algorithms for building a consensus MUL-tree. We give a simple, fast algorithm for building a strict consensus MUL-tree. We also show that although it is NP-hard to find a majority rule consensus MUL-tree, the variant which we call the
singular majority rule consensus MUL-tree
is unique and can be constructed efficiently.