Opening book details…
Can I read An Improved Kernel Size for Rotation Distance in Binary Trees on EtoBox?
An Improved Kernel Size for Rotation Distance in Binary Trees by Joan M. Lucas is a Computer Science article available to read on EtoBox.
What is An Improved Kernel Size for Rotation Distance in Binary Trees about?
Kernelization is one technique for studying intractable problems. By pre-processing a problem instance, and converting it into an equivalent smaller instance, one can substantially lower the time needed to obtain a solution. Cleary and St. John first established the fixedparameter tractability of the problem of determining whether two binary trees are within a distance of k rotations of each other. They showed that the original two trees can be reduced to an equivalent pair of trees each containing at most 5k nodes. In this paper we show an improved bound on the size of the kernel. Using the equivalence of binary trees and convex polygon triangulations, we show that the kernel size is bounded by 2k.
Who reads An Improved Kernel Size for Rotation Distance in Binary Trees?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Joan M. Lucas
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0020-0190)
- Published
- 2010
- Language
- EN
- Field
- Computer Science (Physical Sciences)