On the rotation distance between binary trees

Simple item page
dc.creatorDehornoy, Patrick
dc.date2009-01-16
dc.date.accessioned2026-07-07T12:31:08Z
dc.date.available2026-07-07T12:31:08Z
dc.descriptionWe 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)).
dc.identifierhttps://arxiv.org/abs/0901.2557
dc.identifierhttp://arxiv.org/abs/0901.2557
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/216347
dc.subjectCombinatorics
dc.subject05C12, 20F38, 52B20
dc.titleOn the rotation distance between binary trees
dc.typetext

Files

Collections

arXiv