On the rotation distance between binary trees

DOI10.1016/J.AIM.2009.09.016zbMATH Open1188.05060arXiv0901.2557OpenAlexW2007671720MaRDI 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

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

Cited In (25)

• 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 subword reversing method.
• Common edges in rooted trees and 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)