Next: Zhao Chang-jian and Mihâly Bencze: The Aleksandrov-Fenchel inequality for
Up: TOME 51 (99), no. 1
Previous: Imran Anwar: Janet's Algorithm
Abstract:
To any rooted binary tree we assign a permutation. We define the class "T" of permutations as the set of permutations which come from this assignement. In 1999, Caprara [4] proved it is NP-hard to find a maximal cycle decomposition of the breakpoint graph of a permutation. His result implies that it is NP-hard to sort permutations by reversals, answering a question relevant to Pevzner-Hannenhalli Theory on sorting genomes by reversals. Using Hyperbolic Geometry, Thurston, Sleator and Tarjan(1988) proved that the diameter of the Rotation Graph is 2n-6. In a combinatorial approach to understand how trees evolve under rotations, we found a class "T" of permutations which satisfy the following condition: given any per-mutation, it is possible to decide in linear time if it belongs to "T". If the answer is positive, it is possible to find a maximal cycle decomposition of its breakpoint graph. There is also numerical and topological information shared by the trees and their associated permutation. We prove a result about a number w(T), associated with any tree.
Key Words: Rooted binary trees, rotation distance, sorting by reversals, breakpoint graphs.
2000 Mathematics Subject Classification: Primary: 03D15, Secondary: 68R05.
Download the paper in pdf format here.