# Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree

In * Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms*, pages 1814-1832, 2013.

## Abstract

The triplet and quartet distances are distance measures to compare
two rooted and two unrooted trees, respectively. The leaves of the
two trees should have the same set of *n* labels. The distances are
defined by enumerating all subsets of three labels (triplets) and
four labels (quartets), respectively, and counting how often the
induced topologies in the two input trees are different. In this
paper we present efficient algorithms for computing these
distances. We show how to compute the triplet distance in time *O*(*n*
log *n*) and the quartet distance in time *O*(*d* *n* log *n*),
where *d* is the maximal degree of any node in
the two trees. Within the same time bounds, our framework also allows
us to compute the parameterized triplet and quartet distances, where
a parameter is introduced to weight resolved (binary) topologies
against unresolved (non-binary) topologies. The previous best
algorithm for computing the triplet and parameterized triplet
distances have *O*(*n*^{2}) running time, while the previous best
algorithms for computing the quartet distance include an *O*(*d*^{9} *n*
log *n*) time algorithm and an *O*(*n*^{2.688}) time algorithm, where
the latter can also compute the parameterized quartet
distance. Since *d* ≤ *n*, our algorithms improve on all these
algorithms.

**Copyright notice**
Copyright © 2013 by the Association for Computer Machinery, Inc., and the Society for Industrial and Applied Mathematics.

**Online version**

soda13.pdf (421 Kb)

**DOI**

knowledgecenter.siam.org/0236-000098

**Slides**
soda13.pdf (1531 Kb), soda13.pptx (2215 Kb)

**BIBT**_{E}X entry

@inproceedings{soda13,
author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Christian N{\o}rgaard Storm Pedersen and Thomas Mailund and Andreas Sand",
booktitle = "Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms",
doi = "knowledgecenter.siam.org/0236-000098",
isbn = "978-1-611972-52-8",
issn = "2160-1445",
pages = "1814-1832",
title = "Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree",
year = "2013"
}