Geodesic
Restricted rotation distance between k-ary trees
Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 1, pp. 19-33.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We study restricted rotation distance between ternary and higher-valence trees using approaches based upon generalizations of Thompson's group $F$. We obtain bounds and a method for computing these distances exactly in linear time, as well as a linear-time algorithm for computing rotations needed to realize these distances. Unlike the binary case, the higher-valence notions of rotation distance do not give Tamari lattices, so there are fewer tools for analysis in the higher-valence settings. Higher-valence trees arise in a range of database and filesystem applications where balance is important for efficient performance. 
@article{JGAA_2023_27_1_a1,
     author = {Sean Cleary},
     title = {Restricted rotation distance between k-ary trees},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {19--33},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2023},
     doi = {10.7155/jgaa.00611},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00611/}
}
TY  - JOUR
AU  - Sean Cleary
TI  - Restricted rotation distance between k-ary trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 19
EP  - 33
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00611/
DO  - 10.7155/jgaa.00611
LA  - en
ID  - JGAA_2023_27_1_a1
ER  - 
%0 Journal Article
%A Sean Cleary
%T Restricted rotation distance between k-ary trees
%J Journal of Graph Algorithms and Applications
%D 2023
%P 19-33
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00611/
%R 10.7155/jgaa.00611
%G en
%F JGAA_2023_27_1_a1
Sean Cleary. Restricted rotation distance between k-ary trees. Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 1, pp. 19-33. doi : 10.7155/jgaa.00611. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00611/

Cité par Sources :