An efficient upper bound of the rotation distance of binary trees

DOI10.1016/S0020-0190(00)00008-9MaRDI QIDQ1607028zbMATH OpenWikidataFDO

Authors R. Smith

Publication date 25 July 2002

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

Full work available at URL https://doi.org/10.1016/S0020-0190(00)00008-9

zbMATH Keywords

polynomial time algorithm

Mathematics Subject Classification ID

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

Recommendations

• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• On the rotation distance between binary trees
• scientific article; zbMATH DE number 1161281
• Right-arm rotation distance between binary trees
• On the upper bound on the rotation distance of binary trees

Cites work

• A note on some tree similarity measures
• Enumerating, Ranking and Unranking Binary Trees
• Flipping edges in triangulations
• Generating Binary Trees Lexicographically
• scientific article; zbMATH DE number 4022600 (Why is no real title available?)
• scientific article; zbMATH DE number 1185291 (Why is no real title available?)
• scientific article; zbMATH DE number 1222822 (Why is no real title available?)
• scientific article; zbMATH DE number 758277 (Why is no real title available?)
• scientific article; zbMATH DE number 1418487 (Why is no real title available?)
• On the Average Shape of Binary Trees
• On the cell-growth problem for arbitrary polygons
• On the upper bound on the rotation distance of binary trees
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• The number of coverings in four catalan lattices
• Triangular Dissections of N-Gons
• Triangulating the Circle, at Random

Cited in

(33)

• Generating binary trees by Glivenko classes on Tamari lattices
• Right-arm rotation distance between binary trees
• Bounding restricted rotation distance
• Lower bounds on the rotation distance of binary trees
• Spin network quantum simulator
• Restricted rotation distance between binary trees.
• Common edges in rooted trees and polygonal triangulations
• A Motzkin filter in the Tamari lattice
• Motzkin subposets and Motzkin geodesics in Tamari lattices.
• A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
• The pruning-grafting lattice of binary trees
• A direct algorithm for restricted rotation distance
• Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees
• Computing spin networks
• The edge rotation graph
• Lower Bounds for Accessing Binary Search Trees with Rotations
• scientific article; zbMATH DE number 58304 (Why is no real title available?)
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• scientific article; zbMATH DE number 1222822 (Why is no real title available?)
• scientific article; zbMATH DE number 1439421 (Why is no real title available?)
• Expected maximum vertex valence in pairs of polygonal triangulations
• BOUNDING RIGHT-ARM ROTATION DISTANCES
• An efficient algorithm for estimating rotation distance between two binary trees
• Restricted rotation distance between k-ary trees
• An improved kernel for the flip distance problem on simple convex polygons
• Communication protocols and QECC from the perspective of TQFT. II: QECCs as spacetimes
• Shallow-rotation distance via forest representations
• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• \(k\)-restricted rotation distance between binary trees
• The phagocyte lattice of Dyck words
• Flip distance between two triangulations of a point set is NP-complete
• The Fermat star of binary trees
• Rotation distance is fixed-parameter tractable

Describes a project that uses

Uses Software

• OEIS

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

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