A Linear-Time Approximation Algorithm for Rotation Distance
classification
💻 cs.DS
keywords
distancerotationalgorithmapproximationbinarylinear-timerootedtrees
read the original abstract
Rotation distance between rooted binary trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. We give an efficient, linear-time approximation algorithm, which estimates the rotation distance, within a provable factor of 2, between ordered rooted binary trees. .
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.