Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00212 A Linear-Time Approximation Algorithm for Rotation Distance Sean Cleary and Katherine St. John Vol. 14, no. 2, pp. 385-390, 2010. Concise paper 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. In this short note, we give an efficient, linear-time approximation algorithm, which estimates the rotation distance, within a provable factor of 2, between ordered rooted binary trees.
|
Accepted: August 2010. Reviewed: August 2009. Submitted: July 2009. Final: August 2010. Published: November 2010. Revised: August 2010. Communicated by Tandy Warnow |
| Journal of Graph Algorithms and Applications |