| Autor: |
Cleary, Sean, Maio, Roland |
| Předmět: |
|
| Zdroj: |
Acta Cybernetica; 2022, Vol. 25 Issue 3, p629-646, 18p |
| Abstrakt: |
It is an open question whether there exists a polynomial-time algorithm for computing the rotation distances between pairs of extended ordered binary trees. 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 (S0; T0), 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(n4). [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
