Distributions of restricted rotation distances
From MaRDI portal
Publication:5045245
Abstract: Rotation distances measure the differences in structure between rooted ordered binary trees. The one-dimensional skeleta of associahedra are rotation graphs, where two vertices representing trees are connected by an edge if they differ by a single rotation. There are no known efficient algorithms to compute rotation distance between trees and thus distances in rotation graphs. Limiting the allowed locations of where rotations are permitted gives rise to a number of notions of restricted rotation distances. Allowing rotations at a minimal such set of locations gives restricted rotation distance. There are linear-time algorithms to compute restricted rotation distance, where there are only two permitted locations for rotations to occur. The associated restricted rotation graph has an efficient distance algorithm. There are linear upper and lower bounds on restricted rotation distance with respect to the sizes of the reduced tree pairs. Here, we experimentally investigate the expected restricted rotation distance between two trees selected at random of increasing size and find that it lies typically in a narrow band well within the earlier proven linear upper and lower bounds.
Recommendations
- scientific article; zbMATH DE number 4088743
- On the rotation distance of graphs
- Bounding restricted rotation distance
- A direct algorithm for restricted rotation distance
- DISTRIBUTIONS IN R WITH ROTATIONAL SYMMETRIES1
- Rotation invariant ultradistributions
- Rotation distance for rank bounded trees
- Restricted rotation distance between k-ary trees
- On the induced distribution of the shape of the projection of a randomly rotated configuration
- Effective bounds for the measure of rotations
Cites work
- \(k\)-restricted rotation distance between binary trees
- A linear-time approximation algorithm for rotation distance
- A note on some tree similarity measures
- An efficient sampling algorithm for difficult tree pairs
- Bounding restricted rotation distance
- Common edges in rooted trees and polygonal triangulations
- Computational explorations in Thompson's group F
- Counting difficult tree pairs with respect to the rotation distance problem
- Counting elements and geodesics in Thompson's group \(F\).
- Efficient lower and upper bounds of the diagonal-flip distance between triangulations
- Homotopy Associativity of H-Spaces. I
- scientific article; zbMATH DE number 3900794 (Why is no real title available?)
- scientific article; zbMATH DE number 1178976 (Why is no real title available?)
- Introductory notes on Richard Thompson's groups
- Minimal length elements of Thompson's group \(F\)
- Monoïdes préordonnés et chaînes de Malcev
- Random subgroups of Thompson's group \(F\).
- Restricted rotation distance between binary trees.
- Rotation distance is fixed-parameter tractable
- The associahedron and triangulations of the \(n\)-gon
Cited in
(11)- Bounding restricted rotation distance
- Restricted rotation distance between binary trees.
- DISTRIBUTIONS IN R WITH ROTATIONAL SYMMETRIES1
- scientific article; zbMATH DE number 4088743 (Why is no real title available?)
- Counting difficult tree pairs with respect to the rotation distance problem
- BOUNDING RIGHT-ARM ROTATION DISTANCES
- Algorithms and Data Structures
- Restricted rotation distance between k-ary trees
- The rotation distance of brooms
- \(k\)-restricted rotation distance between binary trees
- Weak associativity and restricted rotation
This page was built for publication: Distributions of restricted rotation distances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5045245)
