The quartet distance[1] is a way of measuring the distance between two phylogenetic trees. It is defined as the number of subsets of four leaves that are not related by the same topology in both trees.
The most straightforward computation of the quartet distance would require time, where is the number of leaves in the trees.
For binary trees, better algorithms have been found to compute the distance in
and
Gerth Stølting Brodal et al. found an algorithm that takes time to compute the quartet distance between two multifurcating trees when is the maximum degree of the trees,[5] which is accessible in C, perl, and the R package Quartet.