Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/115344
Title: Twist-Rotation Transformations of Binary Trees and Arithmetic Expressions
Authors: Li, M.
Zhang, L. 
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.

Page view(s)

30
checked on Mar 9, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.