Restricted rotation distance between binary trees.

DOI10.1016/S0020-0190(02)00315-0zbMATH Open1042.68036OpenAlexW1972564423MaRDI QIDQ1853166FDOQ1853166

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

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

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)

Cites Work

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

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
• An efficient algorithm for estimating rotation distance between two binary trees
• A direct algorithm for restricted rotation distance
• Root-restricted Kleenean rotations
• Right-arm rotation distance between binary trees
• 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
• Title not available (Why is that?)

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)