Restricted rotation distance between binary trees.

DOI10.1016/S0020-0190(02)00315-0zbMath1042.68036OpenAlexW1972564423MaRDI QIDQ1853166

Sean Cleary

Publication date: 21 January 2003

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00315-0

zbMATH Keywords

Binary treesAlgorithms and data structuresRotation distance

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (18)

Restricted rotation distance between k-ary trees ⋮ Generators and normal forms of Richard Thompson's group \(F\) and the four-color theorem ⋮ 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 ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ Effective splaying with restricted rotations ⋮ Root-restricted Kleenean rotations ⋮ Unnamed Item ⋮ Weak associativity and restricted rotation ⋮ Rotation distance is fixed-parameter tractable ⋮ Right-arm rotation distance between binary trees ⋮ Bounding restricted rotation distance

Cites Work

• An infinite-dimensional torsion-free \(\text{FP}_{\infty}\) group
• A note on some tree similarity measures
• Quasi-isometrically embedded subgroups of Thompson's group \(F\)
• Introductory notes on Richard Thompson's groups
• An efficient upper bound of the rotation distance of binary trees
• On the upper bound on the rotation distance of binary trees
• Metrics and embeddings of generalizations of Thompson’s group $F$
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Restricted rotation distance between binary trees.