Restricted rotation distance between binary trees.

DOI10.1016/S0020-0190(02)00315-0MaRDI QIDQ1853166zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Bounding restricted rotation distance
• BOUNDING RIGHT-ARM ROTATION DISTANCES
• \(k\)-restricted rotation distance between binary trees
• Distributions of restricted rotation distances
• Restricted rotation distance between k-ary trees

Cites work

• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 67429 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1418487 (Why is no real title available?)
• scientific article; zbMATH DE number 1439421 (Why is no real title available?)
• A note on some tree similarity measures
• An efficient upper bound of the rotation distance of binary trees
• An infinite-dimensional torsion-free \(\text{FP}_{\infty}\) group
• Introductory notes on Richard Thompson's groups
• Metrics and embeddings of generalizations of Thompson's group \(F\)
• On the upper bound on the rotation distance of binary trees
• Quasi-isometrically embedded subgroups of Thompson's group \(F\)
• Rotation Distance, Triangulations, and Hyperbolic Geometry

Cited in

(20)

• Algorithms and Data Structures
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• \(k\)-restricted rotation distance between binary trees
• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• On the rotation distance between binary trees
• Refined upper bounds for right-arm rotation distances
• Weak associativity and restricted rotation
• Rotation distance is fixed-parameter tractable
• Bounding restricted rotation distance
• Generators and normal forms of Richard Thompson's group \(F\) and the four-color theorem
• BOUNDING RIGHT-ARM ROTATION DISTANCES
• A direct algorithm for restricted rotation distance
• An efficient algorithm for estimating rotation distance between two binary trees
• Right-arm rotation distance between binary trees
• Root-restricted Kleenean rotations
• Distributions of restricted rotation distances
• Effective splaying with restricted rotations
• A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
• Restricted rotation distance between k-ary trees
• scientific article; zbMATH DE number 7527483 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853166)