Please use this identifier to cite or link to this item:
|Title:||Twist-Rotation Transformations of Binary Trees and Arithmetic Expressions||Authors:||Li, M.
|Issue Date:||Aug-1999||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||URI:||http://scholarbank.nus.edu.sg/handle/10635/115344||ISSN:||01966774|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jan 13, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.