The rotation distance of brooms

DOI10.1016/J.EJC.2023.103877arXiv2211.07984OpenAlexW4388786082MaRDI QIDQ6201876FDOQ6201876

Authors: Jean Cardinal, Lionel Pournin, Mario Valencia-Pabon 

Publication date: 26 March 2024

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

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

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)

Cites Work

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

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)