Please use this identifier to cite or link to this item:
|Title:||Twist-Rotation Transformations of Binary Trees and Arithmetic Expressions|
|Citation:||Li, M.,Zhang, L. (1999-08). Twist-Rotation Transformations of Binary Trees and Arithmetic Expressions. Journal of Algorithms 32 (2) : 155-166. ScholarBank@NUS Repository.|
|Abstract:||The paper studies the computational complexity and efficient algorithms for the twist-rotation transformations of binary trees, which is equivalent to the transformation of arithmetic expressions over an associative and commutative binary operation. The main results are (1) a full binary tree with n labeled leaves can be transformed into any other in at most 3n log n + 2n twist and rotation operations, (2) deciding the twist-rotation distance between two binary trees is NP-complete, and (3) the twist-rotation transformation can be approximated with ratio 6 log n + 4 in polynomial time for full binary trees with n uniquely labeled leaves. © 1999 Academic Press.|
|Source Title:||Journal of Algorithms|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Mar 9, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.