@article{Cleary_Maio_2022, title={An Efficient Sampling Algorithm for Difficult Tree Pairs}, volume={25}, url={https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/4138}, DOI={10.14232/actacyb.285522}, abstractNote={<p>It is an open question whether there exists a polynomial-time algorithm for computing the rotation distances between pairs of extended ordered binary trees.<br>The problem of computing the rotation distance between an arbitrary pair of trees, (S, T), can be efficiently reduced to the problem of computing the rotation distance between a difficult pair of trees (S’, T’), where there is no known first step which is guaranteed to be the beginning of a minimal length path. Of interest, therefore, is how to sample such difficult pairs of trees of a fixed size. We show that it is possible to do so efficiently, and present such an algorithm that runs in time O(n<sup>4</sup>).</p>}, number={3}, journal={Acta Cybernetica}, author={Cleary, Sean and Maio, Roland}, year={2022}, month={Jan.}, pages={629-646} }