The rotation distance of brooms

DOI10.1016/J.EJC.2023.103877MaRDI QIDQ6201876OpenAlexFDO

Authors Jean Cardinal, Lionel Pournin, Mario Valencia-Pabon

Publication date 26 March 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

complete split graphbroomsassociahedron of a graph

Mathematics Subject Classification ID

Quadratic programming (90C20) Trees (05C05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Distance in graphs (05C12) Polytopes and polyhedra (52B99)

Abstract: The associahedron $mathcalA(G)$ of a graph $G$ has the property that its vertices can be thought of as the search trees on $G$ and its edges as the rotations between two search trees. If $G$ is a simple path, then $mathcalA(G)$ is the usual associahedron and the search trees on $G$ are binary search trees. Computing distances in the graph of $mathcalA(G)$ (or equivalently, the rotation distance between two binary search trees) is a major open problem. Here, we consider the different case when $G$ is a complete split graph. In that case, $mathcalA(G)$ interpolates between the stellohedron and the permutohedron, and all the search trees on $G$ are brooms. We show that the rotation distance between any two such brooms and therefore the distance between any two vertices in the graph of the associahedron of $G$ can be computed in quasi-quadratic time in the number of vertices of $G$.

Recommendations

• On the diameter of tree associahedra
• scientific article; zbMATH DE number 1161281
• On the rotation distance of graphs
• On the rotation distance between binary trees
• Distributions of restricted rotation distances

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A linear-time approximation algorithm for rotation distance
• A note on some tree similarity measures
• A polynomial case of unconstrained zero-one quadratic optimization
• A realization of graph associahedra
• A type-B associahedron.
• An exact characterization of saturation for permutation matrices
• An improved kernel size for rotation distance in binary trees
• Competitive Online Search Trees on Trees
• Complexity and polynomially solvable special cases of QUBO
• Computing the flip distance between triangulations
• Coxeter complexes and graph-associahedra
• Diameter estimates for graph associahedra
• Edge Conflicts do not Determine Geodesics in the Associahedron
• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• Faces of generalized permutohedra
• Flip distance between triangulations of a planar point set is APX-hard
• Flip distance between two triangulations of a point set is NP-complete
• Graph properties of graph associahedra
• Homotopy Associativity of H-Spaces. I
• Hopf Monoids and Generalized Permutahedra
• Many non-equivalent realizations of the associahedron
• Minimum cost flows, MDPs, and ℓ ₁ -regression in nearly linear time for dense instances
• Minimum cuts and related problems
• Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams
• Monoïdes préordonnés et chaînes de Malcev
• On Rotations and the Generation of Binary Trees
• On the diameter of tree associahedra
• On the self-linking of knots
• Permutation Polyhedra
• Permutohedra, Associahedra, and Beyond
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Rotation distance is fixed-parameter tractable
• Selected Applications of Minimum Cuts in Networks
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• The associahedron and triangulations of the \(n\)-gon
• The asymptotic diameter of cyclohedra
• The diameter of associahedra
• The diameter of type \(D\) associahedra and the non-leaving-face property
• The geometry of flip graphs and mapping class groups
• Triangulations. Structures for algorithms and applications

This page was built for publication: The rotation distance of brooms

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