Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees

Gerth Stølting Brodal, Konstantinos Mampentzidis

We study the problem of computing the triplet distance between two rooted unordered trees with $n$ labeled leafs. Introduced by Dobson 1975, the triplet distance is the number of l…