Home | Issues | About JGAA | Instructions for Authors |
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.
|
Submitted: July 2009.
Reviewed: August 2009.
Revised: August 2010.
Accepted: August 2010.
Final: August 2010.
Published: November 2010.
Communicated by
Tandy Warnow
|
Journal Supporters
|