# A practical *O*(*n* log^{2} *n*) time algorithm for computing the triplet distance on binary trees

In * Proc. 11th Asia Pacific Bioinformatics Conference*. Tsinghua University Press, 2013.

## Abstract

The triplet distance is a distance measure that compares two rooted
trees on the same set of leaves by enumerating all sub-sets of three
leaves and counting how often the induced topologies of the tree are
equal or different. We present an algorithm that computes the
triplet distance between two rooted binary trees in time
*O*(*n*log^{2} *n*). The algorithm is related to an algorithm for
computing the quartet distance between two unrooted binary trees in
time *O*(*n* log *n*). While the quartet distance algorithm
has a very severe overhead in the asymptotic time complexity that
makes it impractical compared to *O*(*n*^{2}) time
algorithms, we show through experiments that the triplet distance
algorithm can be implemented to give a competitive wall-time running
time.

**Online version**
apbc13.pdf (779 Kb)

**BIBT**_{E}X entry

@incollection{apbc13,
author = "Andreas Sand and Gerth St{\o}lting Brodal and Rolf Fagerberg and Christian N{\o}rgaard Storm Pedersen and Thomas Mailund",
booktitle = "Proc. 11th Asia Pacific Bioinformatics Conference",
publisher = "Tsinghua University Press",
title = "A practical $O(n \log^2 n)$ time algorithm for computing the triplet distance on binary trees",
year = "2013"
}