Finding a Maximum Compatible Tree for a Bounded Number of Trees with Bounded Degree Is Solvable in Polynomial Time

摘要

In this paper, we consider the problem of computing a maximum compatible tree for k rooted trees when the maximum degree of all trees is bounded. We show that the problem can be solved in O(2~(2kd)n~k) time, where n is the number of taxa in each tree, and every node in every tree has at most d children. Hence, a maximum compatible tree for k unrooted trees can be found in in O(2~(2kd)n~(k+1)) time.