The rotation distance of brooms
| Autor: | Cardinal, Jean, Pournin, Lionel, Valencia-Pabon, Mario |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The associahedron $\mathcal{A}(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 $\mathcal{A}(G)$ is the usual associahedron and the search trees on $G$ are binary search trees. Computing distances in the graph of $\mathcal{A}(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, $\mathcal{A}(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$. Comment: 26 pages, 3 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|