CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
Englishhe restricted rotation distancedR (S, T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T, where rotations take place at the root of S, or at the right child of the root. A sharp upper bound dR (S, T) ≤ 4 n - 8 is known, based on group theory [S. Cleary, J. Taback, Bounding restricted rotation distance, Information Processing Letters 88 (5) (2003) 251-256]. We refine this bound to a sharp dR (S, T) ≤ 4 n - 8 - ρS - ρT, where ρS and ρT are the numbers of vertices in the rightmost vertex chains of the two trees, using an elementary transformation algorithm. We then generalize the concept to k-restricted rotation, by allowing rotations to take place at all the vertices of the highest k levels of the tree, and study the new distance for k = 2. The case k ≥ 3 is essentially open.
| Autori interni: | |
| Autori: | F. LUCCIO; A. MESA ENRIQUES; PAGLI L |
| Titolo: | K-restricted rotation distance between binary trees |
| Anno del prodotto: | 2007 |
| Digital Object Identifier (DOI): | 10.1016/j.ipl.2006.12.007 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11568/205779
Copyright © 2020