On the rotation distance between binary trees

DOI10.1016/J.AIM.2009.09.016zbMATH Open1188.05060OpenAlexW2007671720MaRDI QIDQ846983FDOQ846983

Authors Patrick Dehornoy

Publication date 16 February 2010

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.2557

zbMATH Keywords

fliptriangulationsThompson's grouprotation distanceBinary tree

Mathematics Subject Classification ID

Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Distance in graphs (05C12) Other groups related to topology or analysis (20F38)

Abstract: We develop combinatorial methods for computing the rotation distance between binary trees, i.e., equivalently, the flip distance between triangulations of a polygon. As an application, we prove that, for each n, there exist size n trees at distance 2n - O(sqrt(n)).

Recommendations

• Lower bounds on the rotation distance of binary trees
• On the upper bound on the rotation distance of binary trees
• Counting difficult tree pairs with respect to the rotation distance problem
• scientific article; zbMATH DE number 1161281
• Refined upper bounds for right-arm rotation distances
• Chain rotations: a new look at tree distance
• Right-arm rotation distance between binary trees
• A linear-time approximation algorithm for rotation distance
• Rotation distance is fixed-parameter tractable
• Algorithms and Data Structures

Cites work

• scientific article; zbMATH DE number 3178652 (Why is no real title available?)
• scientific article; zbMATH DE number 2170467 (Why is no real title available?)
• scientific article; zbMATH DE number 3448564 (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 class of Garside groupoid structures on the pure braid group
• A distance metric on binary trees using lattice-theoretic measures
• Bounding restricted rotation distance
• Cambrian lattices.
• FOREST DIAGRAMS FOR ELEMENTS OF THOMPSON'S GROUP F
• Flips in planar graphs
• Geometric presentations for Thompson's groups.
• Graph of triangulations of a convex polygon and tree of triangulations
• Introductory notes on Richard Thompson's groups
• Left distance binary tree representations
• Minimal length elements of Thompson's group \(F\)
• On Rotations and the Generation of Binary Trees
• On Tamari lattices
• On the upper bound on the rotation distance of binary trees
• Primes, irreducibles and extremal lattices
• Problems of associativity: a simple proof for the lattice property of systems ordered by a semi-associative law
• Restricted rotation distance between binary trees.
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Rotation sequences and edge-colouring of binary tree pairs
• Short notes: Some Properties of the Rotation Lattice of Binary Trees
• Tamari lattices, forests and Thompson monoids
• The rotation graph of binary trees is Hamiltonian
• The structure group for the associativity identity
• Triangle-free triangulations
• Word problems II. The Oxford book

Cited in

(27)

• Common edges in rooted trees and polygonal triangulations
• scientific article; zbMATH DE number 2170467 (Why is no real title available?)
• On the diameter of the rotation graph of binary coupling trees
• On the rotation distance of graphs
• On the diameter of tree associahedra
• scientific article; zbMATH DE number 58304 (Why is no real title available?)
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• The subword reversing method.
• The rotation distance of brooms
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• An efficient upper bound of the rotation distance of binary trees
• Combinatorial flip actions and Gelfand pairs for affine Weyl groups
• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• Finding Eulerian cycle decompositions and the rotation distance between binary trees
• Compatibility fans for graphical nested complexes
• The Euclidean distortion of complete binary trees
• scientific article; zbMATH DE number 1555932 (Why is no real title available?)
• The diameter of associahedra
• On rotation distance of rank bounded trees
• On the upper bound on the rotation distance of binary trees
• Flip distance between two triangulations of a point set is NP-complete
• Extremal distances for subtree transfer operations in binary trees
• Expected maximum vertex valence in pairs of polygonal triangulations
• Celebrating Loday's associahedron
• Rotation distance for rank bounded trees
• Chain rotations: a new look at tree distance
• Lower bounds on the rotation distance of binary trees

This page was built for publication: On the rotation distance between binary trees

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