Geodesic
A Linear-Time Approximation Algorithm for Rotation Distance
Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 385-390.

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

Rotation distance between rooted binary trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. In this short note, we give an efficient, linear-time approximation algorithm, which estimates the rotation distance, within a provable factor of 2, between ordered rooted binary trees. 
@article{JGAA_2010_14_2_a11,
     author = {Sean Cleary and Katherine St. John},
     title = {A {Linear-Time} {Approximation} {Algorithm} for {Rotation} {Distance}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {385--390},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2010},
     doi = {10.7155/jgaa.00212},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00212/}
}
TY  - JOUR
AU  - Sean Cleary
AU  - Katherine St. John
TI  - A Linear-Time Approximation Algorithm for Rotation Distance
JO  - Journal of Graph Algorithms and Applications
PY  - 2010
SP  - 385
EP  - 390
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00212/
DO  - 10.7155/jgaa.00212
LA  - en
ID  - JGAA_2010_14_2_a11
ER  - 
%0 Journal Article
%A Sean Cleary
%A Katherine St. John
%T A Linear-Time Approximation Algorithm for Rotation Distance
%J Journal of Graph Algorithms and Applications
%D 2010
%P 385-390
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00212/
%R 10.7155/jgaa.00212
%G en
%F JGAA_2010_14_2_a11
Sean Cleary; Katherine St. John. A Linear-Time Approximation Algorithm for Rotation Distance. Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 385-390. doi : 10.7155/jgaa.00212. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00212/

Cité par Sources :