An efficient upper bound of the rotation distance of binary trees

DOI10.1016/S0020-0190(00)00008-9zbMath1014.68112WikidataQ60692073 ScholiaQ60692073MaRDI QIDQ1607028

R. Smith

Publication date: 25 July 2002

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

zbMATH Keywords

polynomial time algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (24)

Restricted rotation distance between k-ary trees ⋮ A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations ⋮ BOUNDING RIGHT-ARM ROTATION DISTANCES ⋮ The pruning-grafting lattice of binary trees ⋮ Efficient lower and upper bounds of the diagonal-flip distance between triangulations ⋮ \(k\)-restricted rotation distance between binary trees ⋮ A direct algorithm for restricted rotation distance ⋮ An efficient algorithm for estimating rotation distance between two binary trees ⋮ The phagocyte lattice of Dyck words ⋮ The edge rotation graph ⋮ Lower bounds on the rotation distance of binary trees ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ An improved kernel for the flip distance problem on simple convex polygons ⋮ Flip distance between two triangulations of a point set is NP-complete ⋮ Computing spin networks ⋮ The Fermat star of binary trees ⋮ Rotation distance is fixed-parameter tractable ⋮ Generating binary trees by Glivenko classes on Tamari lattices ⋮ Right-arm rotation distance between binary trees ⋮ Bounding restricted rotation distance ⋮ Spin network quantum simulator ⋮ Restricted rotation distance between binary trees. ⋮ A Motzkin filter in the Tamari lattice ⋮ Motzkin subposets and Motzkin geodesics in Tamari lattices.

Uses Software

• OEIS

Cites Work

• A note on some tree similarity measures
• On the cell-growth problem for arbitrary polygons
• Flipping edges in triangulations
• On the upper bound on the rotation distance of binary trees
• The number of coverings in four catalan lattices
• Enumerating, Ranking and Unranking Binary Trees
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• On the Average Shape of Binary Trees
• Generating Binary Trees Lexicographically
• Triangulating the Circle, at Random
• Triangular Dissections of N-Gons
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An efficient upper bound of the rotation distance of binary trees