Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees

Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1

We present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n^{1.5} log n) time for trees with unbounded degrees, matching the…