Bounding restricted rotation distance

DOI10.1016/j.ipl.2003.08.004zbMath1178.68174OpenAlexW2092060226MaRDI QIDQ1029025

Sean Cleary, Jennifer Taback

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.08.004

zbMATH Keywords

algorithmsdata structuresbinary treesrotation distance

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

Restricted rotation distance between k-ary trees ⋮ A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations ⋮ Distributions of restricted rotation distances ⋮ BOUNDING RIGHT-ARM ROTATION DISTANCES ⋮ Efficient lower and upper bounds of the diagonal-flip distance between triangulations ⋮ \(k\)-restricted rotation distance between binary trees ⋮ On the rotation distance between binary trees ⋮ A direct algorithm for restricted rotation distance ⋮ An efficient algorithm for estimating rotation distance between two binary trees ⋮ Refined upper bounds for right-arm rotation distances ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ Effective splaying with restricted rotations ⋮ Root-restricted Kleenean rotations ⋮ Computing spin networks ⋮ Rotation distance is fixed-parameter tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An infinite-dimensional torsion-free \(\text{FP}_{\infty}\) group
• Introductory notes on Richard Thompson's groups
• Minimal length elements of Thompson's group \(F\)
• An efficient upper bound of the rotation distance of binary trees
• Restricted rotation distance between binary trees.
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Combinatorial properties of Thompson’s group 𝐹