| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428044 | Information Processing Letters | 2009 | 5 Pages |
Abstract
Rotation distance between 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 the case of ordered rooted trees, we show that the rotation distance between two ordered trees is fixed-parameter tractable, in the parameter, k, the rotation distance. The proof relies on the kernelization of the initial trees to trees with size bounded by 5k.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
