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)

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)).

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)

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