Restricted rotation distance between binary trees.

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

Sean Cleary

Publication date: 21 January 2003

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

zbMATH Keywords

Binary trees; Algorithms and data structures; Rotation distance

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

68P05: Data structures

Related Items

BOUNDING RIGHT-ARM ROTATION DISTANCES, An efficient algorithm for estimating rotation distance between two binary trees, A metric for rooted trees with unlabeled vertices based on nested parentheses, 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, Weak associativity and restricted rotation, Rotation distance is fixed-parameter tractable, Right-arm rotation distance between binary trees, Bounding restricted rotation distance, Root-restricted Kleenean rotations, A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations, A direct algorithm for restricted rotation distance, Effective splaying with restricted rotations

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