Per citar aquest document: http://ddd.uab.cat/record/44153
Bounding right-arm rotation distances
Cleary, Sean
Taback, Jennifer
Centre de Recerca Matemàtica

Publicació: Centre de Recerca Matemàtica 2005
Col·lecció: Prepublicacions del Centre de Recerca Matemàtica ; 637
Resum: Rotation distance quantifies the difference in shape between two rooted binary trees of the same size by counting the minimum number of elementary changes needed to transform one tree to the other. We describe several types of rotation distance, and provide upper bounds on distances between trees with a fixed number of nodes with respect to each type. These bounds are obtained by relating each restricted rotation distance to the word length of elements of Thompson's group F with respect to different generating sets, including both finite and infinite generating sets.
Drets: Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús Creative Commons
Llengua: Anglès.
Document: preprint
Matèria: Arbres (Teoria dels grafs)

Adreça alternativa: http://hdl.handle.net/2072/1489


27 p, 239.1 KB

El registre apareix a les col·leccions:
Documents de recerca > Prepublicacions

 Registre creat el 2009-07-13, darrera modificació el 2016-06-11



   Favorit i Compartir